[ 자바스크립트(JavaScript) ] section08 - 4 - 부분집합 구하기(DFS)

📍 section08 - 4 - 부분집합 구하기(DFS)

자연수 n이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 구하여 출력 예제와 같은 순서로 출력하는데 공집합은 출력하지 않는 문제다. N의 범위는 1<=N<=10인데 만약, N이 10개라면 내가 구해야 할 부분집합의 개수는 2^10-1 = 1,024-1(공집합)= 1,023개이다. 재귀적인 방법으로 부분집합을 찾아갈 때 다음처럼 그림을 그리면 이해하기가 쉽다.

 

// 입력
3

// 출력
1 2 3
1 2
1 3
1
2 3
2
3

 

 

1. 길이 N만큼 빈 배열을 0으로 선언한다. (마지막에 index를 출력하면 그것이 부분집합이 된다.)
2. 현재 L레벨 일 때, visit[v] = 1로 선언하여 재귀적으로 순회하고 visit[v] = 0로 선언하여 재귀적으로 순회한다.
3. 한 가지(branch)가 끝나면 값을 출력한다.

 

728x90

 

let n = 3;

console.log(solution(3));

function solution(n) {
    let visit = Array.from({ length: n + 1 }, () => 0); // n번까지 idx가 생겨야하므로
    let answer = [];

    function DFS(v) {
        if (v === n + 1) {  // DFS가 1부터 시작하므로 v가 n+1일때까지 순회해야 정상적으로 index가 출력된다.
            let temp = "";
            for (let i = 0; i < visit.length; i++) {
                if (visit[i]) temp += (i + " ");
            }
            answer.push(temp.trim());
        } else {
            visit[v] = 1;
            DFS(v + 1);
            visit[v] = 0;
            DFS(v + 1);
        }
    }
    DFS(1);
    return answer.join("\n");
}
👉🏽 
1 2 3
1 2 
1 3
1 
2 3
2
3