[Java] PowerSet (멱집합) Algorithm 문제

주어진 집합의 모든 부분집합 = 멱집합

 

 
public class PowerSet {
	private static String[] S = { "a", "b", "c", "d", "e", "f" };
	private static int n = S.length;
	private static boolean[] include = new boolean[n];
	private static int level;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		level = 0;
		powerset(level);
	}
	public static void powerset(int level) {
		if (level == n) {
			for (int i = 0; i < n; i++) {
				if (include[i]) {
					System.out.print(S[i] + " ");
				}
			}
			System.out.println();
			return;
		}
		include[level] = false;
		powerset(level + 1);
		include[level] = true;
		powerset(level + 1);
	}
}

 

깊이우선 탐색으로 각 요소의 포함 유무에 따라 모든 부분집합을 체크