티스토리 뷰

Algorithm

멱집합 Power Set

snail voyager 2020. 4. 20. 18:02
728x90
반응형

집합의 공집합을 포함한 모든 부분 집합
크기는 2 ^ n

public class PowerSet {
static char[] D = {'A', 'B', 'C'};
static boolean[] Visit = new boolean[3];
public static void main(String[] args) {
// TODO Auto-generated method stub
//비트 연산 구현
for(int i=0; i<(1<<3); i++) { // 2^3 탐색
for(int j=0; j<3; j++) {
if((i & (1<<j)) != 0) { // &연산
System.out.print(D[j] + " ");
}
}
System.out.println();
}
System.out.println("\n재귀구현 : ");
powerSet(3, 0);
}
public static void powerSet(int n, int idx) {
if(n == idx) {
for(int i=0; i<n; i++) {
if(Visit[i])
System.out.print(D[i] + " ");
}
System.out.println();
return;
}
Visit[idx] = true;
powerSet(n, idx+1);
Visit[idx] = false;
powerSet(n, idx+1);
}
}
view raw PowerSet.java hosted with ❤ by GitHub
728x90
반응형

'Algorithm' 카테고리의 다른 글

Trie (트라이)  (0) 2024.08.31
위상 정렬 (Topological Sort)  (0) 2022.10.01
순열, 조합, 중복순열, 중복조합  (0) 2020.04.16
최단 경로 알고리즘 - Floyd Warshall  (0) 2020.04.05
최단 경로 알고리즘 - Bellman Ford  (0) 2020.04.05
반응형
300x250