부분집합 구하기(DFS) - Node.js

부분집합 구하기(DFS)

---

문제

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

입력

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

출력

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

입력 예시 1

3

출력 예시 1

123
12
13
1
23
2
3

---

해결방법

function solution(sample_data) {
  let answer = [];
  let channel = Array.from({ length: sample_data }, () => 0);

  function DFS(V) {
    if (V === sample_data + 1) {
      let temp = '';
      for (let i = 1; i <= sample_data; i++) {
        if (channel[i] === 1) {
          temp += i + ' ';
        }
      }
      if (temp.length > 0) {
        answer.push(temp.trim());
      }
    } else {
      channel[V] = 1;
      DFS(V + 1);
      channel[V] = 0;
      DFS(V + 1);
    }
  }
  DFS(1);
  return answer;
}

let sample_data = 3;
console.log(solution(sample_data));

---