[알고리즘]멱집합 (powerset)

data = {a,b,c,d}

어떻게 임의의 집합에 대해 모든 부분집합을 화면에 출력할 수 있을까?

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

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

모든 부분집합을 구하려면,
원소 하나를 제거하고 다른 집합의 부분집합을 구하면 된다.

<< 예 제 >>
함수 powerSet(s) 를 만들었다.
S의 멱집합을 출력하시오

recursion 구현
S가 공집합이라면
출력하기
아니라면
그 중 한원소 t에 대해 t를 제거한 모든 부분집합을 구함;
다시 리커전을 호출해서 t를 제외한 부분집합을 구해서 호출;
그부분집합 출력;
다시 t를 집어넣어서 출력한다;

S-t의 부분집합을 구한 후 그 부분집합들을 한번은 그대로 출력
한번은 t를 추가하여 출력하려면 powerSet이 모든값을 받아서 리턴해줘야
모든것 출력하기 각각 출력하기를 할 수 있다.

수정할 점
powerSet이 단순히 멱집합을 구해서 반환하는것이 아니라 출력하게
반환해줄 필요는 없고 출력하게 해줘라.

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