[Algorithm] 부분집합 구하기(이진트리 DFS)

주어지는 숫자의 부분집합을 구하라는 문제이다. 만약 3이 주어지면 3, 2, 1, (1,2) ... 뭐 이런식이다. 

 

const input = require("fs").readFileSync("example.txt").toString();
const n = Number(input);
const visited = new Array(n + 1).fill(0);
let ans = [];
const DFS = (num) => {
  if (num === n + 1) {
    let k = [];
    for (let i = 1; i <= n; i++) {
      if (visited[i] == 1) {
        k.push(i);
      }
    }
    ans.push(k);
    return;
  } else {
    visited[num] = 1;
    DFS(num + 1);
    visited[num] = 0;
    DFS(num + 1);
  }
};
DFS(1);
let answer = ""
for (let line of ans) {
  answer += line.join(" ") + "\n" 
}
console.log(answer.trim());

포함시키고 안시키고를 어떻게 해야하는지 고민이 되었다. 아직 DFS가 체화가 안된 듯하다. 동작원리는 알겠는데 코드로 구현하는데까지는 아직 멀었다. if에는 함수의 종료를 나타내고 else가 조건처리인데 이 부분은 동빈나가 이야기했던 부분이었다. 김태원 강의가 좋았던 점은 진짜 초심자 수준에서 해줘서 눈높이 교육이다. 동빈나의 경우 이 깊이를 만나면 종료한다라고 설명하니까 알듯말듯했는데 김태원님 강의는 콜스택 그려서 하니 이해가 안될 수 없도록 만들어준다. 동빈나 강좌를 탓하기 보다는 아직 내 내공이 부족한 걸로... 재귀함수가 나에겐 정말 큰 벽처럼 느껴졌는데 그 벽이 점점 허물어지는 것을 느낀다.