Powerset

집합 S 의 모든 부분집합을 구하라.

step 1

• {a,b,c,d,e,f} 의 모든 부분집합을 나열하려면
  • a를 제외한 {b,c,d,e,f}의 모든 부분집합들을 나열하고
  • {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.

step2

• {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면
  • {c,d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고
  • {c,d,e,f,}의 모든 부분집합에 {a,b}를 추가한 집합들을 나열한다.

step3

• {c,d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하려면
  • {d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고
  • {d,e,f}의 모든 부분집합들에 {a,c}를 추가한 집합들을 나열한다.

Mission : 집합 S의 PowerSet 을 출력하라

powerSet(s) 
    if S is an empty set
        print nothing;
    else
        let t be the first element of S;
        find all subset of S-{t} by calling powerSet(S-{t});
        print the subset;
        print the subsets with adding t;

powerSet(P, S) 
    if S is an empty set
        print P;
    else
        let t be the first element of S;
        powerSet(P, S-{t});
        powerSet(P U {t}, S-{t});

recursion 함수가 두개의 집합을 매개변수로 받도록 설계해야한다. 두번째 집합의 모든 부분집합들에 첫번째 집합을 합집합하여 출력한다.

private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
private static int n=data.length;
private static boolean [] include = new boolean [n];

public static void powerSet(int k) {
    if (k==n) {
        for (int i=0; i<n; i++)
            if (include[i]) System.out.print(data[i] + " ");
        System.out.println();
        return;
    }

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

k : 트리상에서 현재 나의 위치를 표현한다.

if (k==n) : 만약 내 위치가 리프노드라면

include[k] = false : 먼저 왼쪽으로 내려 갔다가

include[k] = true : 이번엔 오른쪽으로 내려 간다