Recursion - 멱집합

멱집합

주어진 집합의 모든 부분집합들을 원소로 가지는 집합이다

개수를 구하는 공식은 집합 원소의 개수가 n이라고 가정하면

2^n이다

{a,b} 라면
2^2= 4
{a}, {b}, {a,b}, {∅}

접근 방법

{a,b}의 모든 부분 집합을 구하는 방법은 a를 제외한 모든 원소의 부분 집합을 구한 뒤에 (1)

(1)의 집합에 a를 추가해줘서 (2)

(1),(2)를 다 나열하는 것이다

(1) = {b}, {∅}
(2) = {a,b}, {a}

둘을 합치면 {a}, {b}, {a,b}, {∅}로 모든 원소를 나열할 수 있게 된다

여기서 재귀적인 부분을 찾아 재귀적으로 해결할 수 있다

내가 푼 코드

모든 부분 집합을 출력하는게 목적

접때 실패한 기억을 떠올려서 이번엔 base case를 먼저 작성하기로 했다

재귀 호출이 끝나기 위해서는 더이상 구할 부분 집합이 없을 때이다

그래서 집합 s의 길이가 0일 때를 base case로 정했다

하지만..

그거 외에는 한게 없다

구현

여러 설명이 있었지만 나는 깊이 우선 탐색으로 접근하는 것이 제일 이해가 쉬웠다

각 노드는 각 원소를 포함시킬지 시키지 않을지를 정한 경우의 수이다

트리의 높이가 1일 때 a를 포함 시킨 경우, 그렇지 않은 경우 2가지

2일 땐 위의 두 경우 각각에서 b를 포함 시킨 경우 그렇지 않은 경우 총 4가지

3일 땐 위의 네 경우 각각에서 c를 포함 시킨 경우 그렇지 않은 경우 총 8가지가 나오게 된다

이 트리를 모두 탐색하게 되면 우리가 원하는 해를 모두 구할 수 있는게 되는데

깊이 우선 탐색으로 트리를 순회하면 되겠다

const s = ['a','b','c','d','e','f','g'];
const include = Array(s.length);
const answer = [];

function powerSet(k) {
    if(k===s.length){
        let str = '';
        for(let i=0; i<include.length;i++){
            if(include[i]) str += s[i];
        }

        return answer.push(`{${str}}`);
    }

    include[k]=false;
    powerSet(k+1);

    include[k]=true;
    powerSet(k+1);
}

powerSet(0);

include 배열은 bool값만 들어가는 배열로 집합과 같은 길이를 가지며 true일 경우 동일 인덱스의 집합 원소가 포함 false일 경우 포함하지 않는 경우이다