부분 집합 알고리즘

따로 정해진 이름이 있는 알고리즘이라기 보단 문제를 접해보니 비슷한 패턴이 보여서 정리해두려고 글을 쓴다.

추가

처음에 이 글을 쓸 때 명확하지 않았던 개념이 시간이 지나 이해도가 높아져서 추가 설명을 붙이려한다.
이 패턴 역시 백트래킹의 일종이다. dfs로 모든 경우를 탐색하면서 원하는 부분은 check 또는 값을 누적하는 것이다.

// 부분 집합 구하기
function solution(n) {
  let answer = [];
  let check = Array.from({ length: n + 1 }, () => 0); //[0,0,0,0]
  function DFS(L) {
    if (L === n + 1) {
      let tmp = "";
      for (let i = 1; i <= n; i++) {
        if (check[i] === 1) tmp += i + " ";
      }
      if (tmp.length > 0) answer.push(tmp.trim());
    } else {
      check[L] = 1;
      DFS(L + 1); //부분집합에 참여.
      check[L] = 0;
      DFS(L + 1); // 부분집합에 참여하지 않음.
    }
  }
  DFS(1);
  return answer;
}

//[ '1 2 3', '1 2', '1 3', '1', '2 3', '2', '3' ]

기본 패턴이다. 내부함수에 Level 변수를 이용해 깊이 탐색을 하는 방식이고 참여하는 경우와 참여하지 않는 케이스를 나눌 때 사용하면 쉽게 문제를 풀 수 있다.

// 합이 같은 부분 집합
function solution(arr) {
  let answer = "NO",
    flag = 0;
  let total = arr.reduce((a, b) => a + b, 0);
  let n = arr.length;
  function DFS(L, sum) {
    if (flag) return;
    if (L === n) {
      if (total - sum === sum) {
        answer = "YES";
        flag = 1; // 깃발, 더 돌 필요는 없으니까.
      }
    } else {
      DFS(L + 1, sum + arr[L]);
      DFS(L + 1, sum);
    }
  }
  DFS(0, 0);
  return answer;
}

앞 문제와 같은 패턴이 보이는가?

// DFS 내부의 조건문
if (L === n) {
      // 리턴 또는 수행해야하는 작업
    } else {
     // 재귀 호출
    }
  }
}
// DFS 최초의 호출
DFS();

이런 유형의 특징은 일단 탐색을 다하기는 해야 한다는 점이다. 문제마다 따로 조건이 있어서 답이 다 다르고 하는 것이지만 일단 그 답을 찾기전까지는 계속 탐색을 해나간다는 소리이다.

// 최대값을 구하는 문제 limit가 주어지고 거기에 가장 가까운 값을 구한다.
function solution(c, arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let n = arr.length;
  function DFS(L, sum) {
    if (sum > c) return;
    if (L === n) {
      // 최대레벨
      answer = Math.max(answer, sum);
    } else {
      DFS(L + 1, sum + arr[L]);
      DFS(L + 1, sum);
    }
  }
  DFS(0, 0);
  return answer;
}
let arr = [81, 58, 42, 33, 61];
// 242

포함하는지 하지 않는지를 생각해야되는 문제에 적용해보자