IF - 부분집합

문제

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

예시

Input	Output
3	["123","12","13","1","23","2","3"]

풀이 및 회고

• 1~N 까지의 수로 만들 수 있는 모든 문자열 집합을 탐색하는 문제이다.
• 1~N 까지의 각 숫자는 각 집합 마다 자신이 포함되느냐, 포함되지 않느냐로 나뉜다.
• 따라서 1~N 까지의 이진 트리를 그려서 N 이 1 씩 커질 때 마다 해당 수가 포함되는 경우와 포함되지 않는 경우를 모두 탐색하면 된다.
• 각 숫자의 집합 내 포함 여부를 가리기 위해 N 길이 만큼 1을 채워넣은 체크용 배열 arr 로 각 숫자가 포함 될 때와 포함되지 않을 때를 나눠서 탐색한다.

코드

const solution = (num) => {
  const answer = [];
  let result = "";
  const arr = new Array(num);
  arr.fill(1);

  const DFS = (dt) => {
    if (dt === num + 1) {
      for (let i = 1; i <= arr.length; i++) {
        if (arr[i] === 1) result += i;
      }
      result && answer.push(result);
      result = "";
    } else {
      arr[dt] = 1;
      DFS(dt + 1);
      arr[dt] = 0;
      DFS(dt + 1);
    }
  };

  DFS(1);
  return answer;
};