8-4. 부분 집합 구하기(DFS)

문제

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

풀이

function solution(n) {
  let answer = [];
  let ch = Array.from({ length: n + 1 }, () => 0);
  console.log(ch);
  function DFS(V) {
    if (V === n + 1) {
      let tmp = "";
      console.log(ch);
      for (let i = 1; i <= n; i++) {
        if (ch[i] === 1) tmp += i + " ";
      }
      if (tmp.length > 0) answer.push(tmp.trim());
      console.log(tmp);
    } else {
      ch[V] = 1;
      DFS(V + 1);
      ch[V] = 0;
      DFS(V + 1);
    }
  }

  DFS(1);
  return answer;
}

console.log(solution(3));

재귀함수 로직 구조

 

재귀함수 ch 배열을 통한 조합 구성(그림을 잘 못그립니다.)