부분집합 구하기(DFS)

원동휘·2022년 12월 26일
0

NOTE - 코테

목록 보기
34/42

< 문제 >

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
▣ 출력설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다.
▣ 입력예제 1 3
▣ 출력예제 1 123
12
13
1 23 2
3

풀이

// 부분집합 구하기(DFS)
function solution(n) {
  let answer = [];
  // 각 탐색을 구별할 0으로 구성된 배열 작성 (첫번째 자리는 무시)
  let ch = Array.from({ length: n + 1 }, () => 0);
  function DFS(v) {
    // n + 1 = 4
    if (v === n + 1) {
      let temp = '';
      for (let i = 1; i <= n; i++) {
        if (ch[i] === 1) temp += i + ' ';
      }
      //공집합은 출력하지 않습니다.
      temp.length > 0 && answer.push(temp.trim());
    } else {
      ch[v] = 1;
      DFS(v + 1);
      ch[v] = 0;
      DFS(v + 1);
    }
  }
  DFS(1);

  return answer;
}

console.log(solution(3));
profile
Front-End Developer #Nextjs #React #Typescript

0개의 댓글