[Algorithm] 부분집합 구하기(DFS)

❐ 부분집합 구하기

▶︎ 문제

   자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하시오.
   단, 공집합은 출력하지 않습니다.

 

▷ 입력 예제

3

 

▶︎ 출력 예제

1 2 3
1 2 
1 3
1
2 3
2
3

 

▷ 내 답안

function solution(n) {
    let answer = "";
    let ch = Array.from({ length: n + 1 }, () => 0);
    function DFS(L) {
        if (L > n) {
            ch.forEach((ele, i) => {
                if (ele === 1) {
                    answer = answer + i.toString();
                }
            });
            answer = "";
            return;
        } else {
            ch[L] = 1;
            DFS(L + 1);
            ch[L] = 0;
            DFS(L + 1);
        }
    }
    DFS(1);
}

console.log(solution(3));

 

푸는데 시간이 꽤 많이 걸렸다. 출력값은 잘 나오는데 내가 이진트리탐색을 완전히 이해해서 푼 것 같지 않은 아쉬움이 있다.

 

문제를 푸는 원리는 이렇다. 1-3의 원소를 갖는 집합에는 기본적으로 1,2,3의 수가 들어있을 것이다. 그리고 각각의 수는 부분집합 안에 들어 있을수도, 들어 있지 않을 수도 있는 2가지 경우의 수를 가지기 때문에 부분집합의 갯수는 2의 3승, 즉 8이 된다. (다만 이 문제에서는 공집합을 제외하고 출력하기로 한다)

 

 

그림을 통해 이진트리로 나타낸 모습이다. 

 

 

let ch = Array.from({length: n+1}, () => 0)

값을 체크하는 배열을 만드는데 이때 길이는 n+1이 된다. 그 이유는 index번호를 활용하기 위해서다.(인덱스는 0부터 카운트되기 때문) 

 

        if (L > n) {
            ch.forEach((ele, i) => {
                if (ele === 1) {
                    answer = answer + i.toString();
                }
            });
            answer = "";
            return;
        } else {
            ch[L] = 1;
            DFS(L + 1);
            ch[L] = 0;
            DFS(L + 1);
        }

else 문의 코드는 인덱스가 L인 자리에 해당하는 값을 계속 바꾸면서 DFS(4)까지 나아간다. DFS(4)가 실행되면 이진트리 끝에 다다랐으므로 if문이 동작한 후 종료되고, 실행스택에 있는 DFS(3)로 다시 돌아가 인덱스가 L인 자리에 해당하는 값을 0으로 바꾸고 다시 DFS(4)가 실행스택에 들어간다.

이와 같은 과정이 계속 반복된다. (어렵다....)

 

DFS를 이용해 부분집합을 출력하는 문제였다. 확실히 어렵고 아직도 완벽히 이해한 것 같지 않지만 개발이 항상 나에게 그랬듯 계속 노력하다보면 깨닫는 순간이 금방 올거라 믿는다!