2022/03/29) 4. 부분집합 구하기 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<부분집합 구하기>
: 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성한다. 공집합은 출력하지 않는다.

2. 해결 방법

1. 먼저 뿌리는 1부터 시작해서 뻗어가야 하므로, DFS함수에서 1값을 받아와야 한다. 그러므로 v변수를 하나 더 만든다고 생각한다. 그러다가 v===n+1이 되면 for문으로 체크배열의 값을 읽어서 tmp에 넣어준다. 추가로 공집합은 제외해야 하므로 tmp.length>0일 경우에만 answer에 push해준다. (공집합도 DFS문의 if문에 들어오므로 tmp=""가 만들어짐. 그래서 조건을 주지 않으면 push됨)
   체크배열은 0,1,2,3 총 길이가 3이 아닌 4인 배열인데, 인덱스가 1이 아닌 0부터 시작하므로 바로 값을 대입하기 위해서 이렇게 하는 거다. 인덱스 0번의 역할은 없다.
2. '포함'인지, '불포함'인지가 핵심이다!!!

3. 정답

        <script>
            function solution(n){
                let answer=[];
                let ch = Array.from( {length:n+1}, ()=> 0 );
                function DFS(v){
                    if(v === 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[v]=1; //1은 포함된 거, 0은 포함되지 않은 거
                        DFS(v+1);
                        ch[v]=0;
                        DFS(v+1);
                    }
                }
                DFS(1);
                return answer;
            }
            console.log(solution(3));
        </script>