[JavaScript/section 8] 04 - 부분집합 구하기

📌 04 - 부분집합 구하기(DFS)

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 문제이다. 첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래의 출력예제와 같은 순서로 출력해야 한다. 단, 공집합은 출력하지 않는다.

입력예제
3
출력예제
1 2 3
1 2
1 3
1
2 3
2
3

부분집합의 개수는 2^N 이지만 공집합은 출력하지 않으므로 -1을 해준다. N이 3이면 출력해야하는 부분집합의 개수는 7개가 된다. 재귀함수를 이용해 부분집합을 찾아갈 때 다음과 같이 그림을 그리면서 이해를 하면 도움이 된다.

 

📝 소스 코드

function solution(n) {
  let answer = [];
  let ch = Array.from({ length: n + 1 }, () => 0);
  
  function DFS(v) {
    if (v === n + 1) {
      let tmp = '';
      for (let i = 1; i <= n; i++) {
        if (ch[i] === 1) tmp += i + ' ';
      }
      if (tmp.length > 0) answer.push(tmp.trim());
    } else {
      ch[v] = 1; // 포함 한다.
      DFS(v + 1);
      ch[v] = 0; // 포함 안한다.
      DFS(v + 1);
    }
  }
  DFS(1);

  answer = answer.join('\n');
  return answer;
}

console.log(solution(3));