[Algorithm] 부분집합에 대해서 with Java

부분집합이란?

어떤 집합 S = {1, 2, 3}이 주어졌을 때, 이 집합에서 만들 수 있는 부분집합은 다음과 같다.

{}
{1}, {2}, {3}
{1,2}, {1,3}, {2,3}
{1,2,3}

즉, 원소가 N개인 집합에서 만들 수 있는 부분집합의 개수는 2^N개이다.
각 원소를 포함할지 말지를 결정하면 되므로 N개의 원소에 대해 각각 "선택" 또는 "비선택" (2가지 선택지)가 주어지기 때문이다.

 

재귀함수를 이용한 부분집합 with Java

import java.io.BufferedReader;
import java.io.InputStreamReader;

// 부분집합: 재귀함수 버전
public class SubSet {

	private static int N;
	private static int[] input;  // 입력받은 원소들
	private static boolean[] isSelected;  // 각 원소가 부분집합의 구성에 포함되었는지 여부

	// cnt: 직전까지 고려한 원소의 개수
	private static void generatedSubSet(int cnt) {

		// 기저부분
		if (cnt == N) {
			for (int i = 0; i < N; i++) {
				System.out.print((isSelected[i] ? input[i] : "X") + " ");
			}
			System.out.println();
			return;
		}

		// 유도부분
		// 현재 원소를 부분집합 구성에 포함
		isSelected[cnt] = true;
		generatedSubSet(cnt + 1);

		// 현재 원소를 부분집합 구성에 미포함
		isSelected[cnt] = false;
		generatedSubSet(cnt + 1);
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(in.readLine());
		
		input = new int[N];
		isSelected = new boolean[N];
		
		String[] split = in.readLine().split(" ");
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(split[i]);
		}

		generatedSubSet(0);
	}

}

핵심 로직 (재귀 호출 흐름)

1. 기저 조건 (Base Case)
   • cnt == N이면 모든 원소를 선택할지 여부를 결정한 것이므로, 결과를 출력하고 종료합니다.
2. 재귀 호출 (Recursive Calls)
   • isSelected[cnt] = true; → 현재 원소를 선택하고 다음 원소 탐색
   • isSelected[cnt] = false; → 현재 원소를 선택하지 않고 다음 원소 탐색

 

재귀호출 과정

                           []
                 /                  \
              [1]                    []
           /       \                /     \
       [1,2]      [1]            [2]       []
      /    \     /    \         /    \     /   \
 [1,2,3] [1,2] [1,3]  [1]    [2,3] [2]   [3]   []

위 트리는 모든 부분집합을 만들기 위해 재귀적으로 탐색되는 과정을 시각화한 것이다.

 

재귀함수 코드 실행결과

1 2 3 
1 2 X 
1 X 3 
1 X X 
X 2 3 
X 2 X 
X X 3 
X X X

이 결과는 모든 부분집합을 표현한 것이다.

• X는 해당 원소가 부분집합에서 제외되었음을 의미한다.
• {1,2,3}, {1,2}, {1,3}, {1}, {2,3}, {2}, {3}, {} 부분집합이 생성되었다.

 

비트마스킹을 이용한 부분집합 생성

import java.io.BufferedReader;
import java.io.InputStreamReader;

// N개의 원소를 입력받아 가능한 모든 부분집합 생성
// 1 <= N <= 10
public class S4_SubSetBinaryCounting {
	
	private static int N;
	private static int[] input;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(in.readLine());
		input = new int[N];
		
		String[] split = in.readLine().split(" ");
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(split[i]);
		}
		
		generateSubSet();
	}
	
	private static void generateSubSet() {
		
		for (int flag = 0; flag < (1 << N); flag++) {  // 유도부분 대체하여 반복문으로 부분집합 구함
		
			for (int i = 0; i < N; i++) {
				System.out.print(((flag & (1 << i)) != 0 ? input[i] : "X") + " ");
			}
			System.out.println();
		}
		
	}
}