Programming/Code
[Java] PowerSet (멱집합) Algorithm 문제
MIN JOON
2017. 10. 12. 10:16
주어진 집합의 모든 부분집합 = 멱집합
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);
}
}
깊이우선 탐색으로 각 요소의 포함 유무에 따라 모든 부분집합을 체크