부분집합 구하기(백트래킹)

문제

제한사항

입출력 예

풀이

function solution2(n) {
  let answer = [];
  let tmp = new Array(n + 1).fill(0);

  function dfs(v) {
    if (v === n + 1) {
      let put = '';
      for (let i = 0; i <= n; i++) {
        if (tmp[i]) {
          put += i;
        }
      }
      answer.push(put);
    } else {
      tmp[v] = 1;
      dfs(v + 1);
      tmp[v] = 0;
      dfs(v + 1);
    }
  }
  dfs(1);
  return answer.filter((e) => e.length);
}

console.log(solution2(3));

• 부분집합 알고리즘을 따로 정리한 글이 있다.
• 가볍게 다시 설명을 하자면 사용을 하느냐 안하느냐의 관점으로 문제를 풀면 이해가 쉽다.
• 부분집합에 1을 사용할 것인지 아닌지를 판단하는 거고 그것을 판단하기 위한 tmp배열을 만들어 사용했다.
• 사용을 한다면 tmp배열에 1을 할당하고 재귀를 호출, 사용하지 않을 것이라면 tmp배열에 0을 할당하고 재귀를 호출한다.