[알고리즘/인프런] 부분집합

문제 

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

 

풀이

#1처럼 재귀 함수의 매개변수로 누적값을 전달하는 경우, 콜스택에서 최상단 함수 실행 컨텍스트가 제거 되었을 때 이전 함수 실행 시의 값을 기억하고 있기 때문에 각 재귀를 돌기 전에 해당 값을 포함할 지의 여부를 결정해주지 않아도 된다.

그렇지 않은 경우, #2과 같이 부분집합에 어떤 값을 포함할지의 여부를 체크하는 배열을 이용할 수 있다.

 

#1

function solution(n) {
  function DFS(L, res) {
    if (L === n + 1) console.log(res);
    else {
      DFS(L + 1, res + " " + L); // 부분집합에 포함 O
      DFS(L + 1, res); // 부분집합에 포함 X
    }
  }
  DFS(1, "");
}

 

#2

function solution(n) {
  let ch = Array.from({ length: n + 1 }, () => 0);

  function DFS(v) {
    if (v === n + 1) {
      console.log(
        ch
          .map((num, idx) => {
            if (num === 1) return idx;
          })
          .filter((num) => num > 0)
          .join(" ")
          .trim()
      );
    } else {
      ch[v] = 1; // 부분집합에 포함 O
      DFS(v + 1);
      ch[v] = 0; // 부분집합에 포함 X
      DFS(v + 1);
    }
  }

  DFS(1);
}