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

알고리즘/코딩테스트 공부

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

YG - 96년생 , 강아지 있음, 개발자 희망 2022. 3. 24. 04:38

문제

자연수 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));