[알고리즘] 순환(Recursion) 07 - 멱집합(상태공간트리)

순환(Recursion) 응용편 : 멱집합

인프론 강의를 보면서 연습하고 기록하고 있습니다

의사코드

powerSet(P, S){ //S의 멱집합을 구한 후 각각의 집합 P를 합집합하여 출력
	if S is an empty set{
		print P;
	}else{
		let t be the first element of S;
		powerSet(P, S-{t}); //t를 포함하지 않는 부분집합
		powerSet(Pu{t}, S-{t}); //t를 반드시 포31
		// recursion 함수가 두 개의 집합을 매개변수로 받도록 설계
		// 두 번째 집합의 모든 부분집합들에 첫번째 집합을 합집합하여 출력
	}
}

Java코드

private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
private static int n = data.length;
//int k와 함께 트리상에서 현재 나의 위치를 표현
private static boolean[] include = new boolean[n];

public static void main(String[] args) {
	powerSet(0);
}

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;
	}

	//data[k]를 포함하지 않는 경우
	include[k] = false;
	powerSet(k+1);

	//data[k]를 포함하는 경우
	include[k] = true;
	powerSet(k+1);
}

f
e
e f
d
d f
d e
d e f
c
c f
c e
c e f
c d
c d f
c d e
c d e f
b
b f
b e
b e f
b d
b d f
b d e
b d e f
b c
b c f
b c e
b c e f
b c d
b c d f
b c d e
b c d e f
a
a f
a e
a e f
a d
a d f
a d e
a d e f
a c
a c f
a c e
a c e f
a c d
a c d f
a c d e
a c d e f
a b
a b f
a b e
a b e f
a b d
a b d f
a b d e
a b d e f
a b c
a b c f
a b c e
a b c e f
a b c d
a b c d f
a b c d e
a b c d e f