어떤 지합의 공집합과 자기 자신을 포함한 모든 부분집합을 powerset이라고 한다.
만약 어떤 집합의 원소 개수가 n
개일 경우 그 집합의 부분집합 개수는 2^n
개가 된다.
아래 그림은 부분집합을 구하는 과정이다.
배열의 크기는 집합의 원소 개수이다.
백트래킹을 활용하여 부분집합을 구한다.
import java.io.*;
import java.util.*;
public class test {
static int N; // 집합 원소의 개수
static int[] subSetArr; // 부분집합을 담는 배열
static int[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
subSetArr = new int[N];
subSet(0);
}
static void subSet(int deep) {
if(deep == N) {
makeSubSet();
return;
}
subSet(deep+1);
subSetArr[deep] = 1;
subSet(deep+1);
subSetArr[deep] = 0;
}
static void makeSubSet() {
String s = "";
for(int i=0; i<N; i++) {
if(subSetArr[i] == 1) s += i + " ";
}
System.out.println(s);
}
}
[입력-출력 예시]
집합 원소의 개수가 3일 경우 그 집합의 부분집합 인덱스를 출력
3
2
1
1 2
0
0 2
0 1
0 1 2