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

문제(출처 : 인프런 자바스크립트 알고리즘 문제풀이 강의, 정보올림피아드)

 

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

 

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

 

▣ 출력설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다.

 

▣ 입력예제 1 3

 

▣ 출력예제 1

123
12
13

1 23 2
3

Tip

 

문제풀이

//정답
function solution(n){
    let answer=[];
    let ch=Array.from({length:n+1}, ()=>0);
    function DFS(L){
        if(L===n+1){
            let tmp="";
            for(let i=1; i<=n; i++){
                if(ch[i]===1) tmp+=(i+" ");
            }
            if(tmp.length>0) answer.push(tmp.trim()); //공집합 제외
        }
        else{
            ch[L]=1;
            DFS(L+1);
            ch[L]=0;
            DFS(L+1);
        }
    }
    DFS(1);
    return answer;
}

console.log(solution(3));