[Algorithm] 부분집합 구하기 (DFS) (javaScript)

문제

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.

입력설명

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

출력설명

첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다.

입출력예제

입력
3

출력
1 2 3
1 2
1 3
1
2 3
2
3

문제 해결

const solution = (num) => {
  let answer = "";
  const checkArr = new Array(num + 1).fill(0);

  const dfs = (vertex) => {
    if (vertex === num + 1) {
      let tmp = "";
      for (let i = 1; i <= num; i++) {
        if (checkArr[i] === 1) tmp += i + " ";
      }
      if (tmp.length > 0) answer += tmp.trim() + "\n";
    } else {
      checkArr[vertex] = 1;
      dfs(vertex + 1);
      checkArr[vertex] = 0;
      dfs(vertex + 1);
    }
  };

  dfs(1);
  return answer;
};

const tmp = solution(3);
console.log(tmp); // 123 12 13 1 23 2 3