멱집합(PowerSet)

a가 들어가거나 안 들어가거나

b가 들어가거나 안 들어가거나

...

f가 들어가거나 안 들어가는 모든 경우의 수는 2^n이다.(n은 원소의 개수)

pick이라는 boolean 배열을 두고 해당 인덱스에 원소를 뽑았을 경우 true, 안 뽑았을 경우를 false라고 두고 재귀적으로 구현했다.

import java.util.*;
public class Main {
	private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
	private static boolean [] pick = new boolean[6];
	private static int n = data.length;
	
	public static void main(String[] args){
		powerSet(0);
	}

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

 

상태공간트리(state space tree)로 따지면

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

이 부분은 왼쪽 자식 노드 탐색

pick[k] = true;
powerSet(k+1);

이 부분은 오른쪽 자식 노드 탐색이다. 

k==n인 경우는 리프노드에 도달했을 경우이다.