[Algorithm] 부분집합 (JAVA)

[부분집합]

어떤 지합의 공집합과 자기 자신을 포함한 모든 부분집합을 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