---

⚡ 부분집합과 조합

---

📌 부분집합

🔷 부분집합의 수

• 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다.
• 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.

import java.util.Arrays;

public class DailyClass {
	public static String[] 재료 = {"오이", "우엉", "햄", "참치"};

	public static void main(String[] args) {
		int  N = 4;
		int [] sel = new int [N];
		
		for(int a = 0; a < 2; a++) {
			sel[0] = a;
			for(int b = 0; b < 2; b++) {
				sel[1] = b;
				for(int c = 0; c < 2; c++) {
					sel[2] = c;
					for(int d = 0; d < 2; d++) {
						sel[3] = d;
						System.out.println(Arrays.toString(sel));
						for(int i = 0; i < N; i++) {
							if(sel[i] == 1) {
								System.out.print(재료[i]);
							}
						}
						System.out.println(":김밥");
					}
				}
			}
		}
	}
}

💡 모든 부분집합을 구하는 이 코드를 비트마스킹을 통해 적은 반복문으로 구현할 수 있다.

public class 부분집합 {
	public static String[] 재료 = {"오이", "우엉", "햄", "참치"};

	public static void main(String[] args) {
		int  N = 4;
		int [] sel = new int [N];
		
		// i는 모든 부분집합
		for(int i = 0; i < (1 << N); i++) {
			System.out.println(i);
			// 재료 검사
			// i & (비트 << 옮긴 횟수) => 1, 2, 4, 8, ..., 2^j
			for(int j = 0; j < N; j++) {
				if((i & (1<<j)) > 0) {
					System.out.print(재료[j]);
				}
			}
			System.out.println(":김밥");
		}
	}

}

💡 재귀함수로도 구현할 수 있다.

public class 부분집합 {
	public static String[] 재료 = {"오이", "우엉", "햄", "참치"};
	static int N = 4;
	static boolean [] sel = new boolean [N];
	
	public static void main(String[] args) {
		powerset(0);
	}
	
	// idx: 해당 위치 판단
	public static void powerset(int idx) {
		// 기저파트
		if(idx == N) { // 모든 재료를 다 판단했을 때
			for(int i = 0; i < N; i++) {
				if(sel[i])
					System.out.print(재료[i]);
			}
			System.out.println();
			return;
		}
		
		// 재귀파트 (두 문단의 순서가 바뀌면 출력 순서가 바뀐다)
		sel[idx] = true;
		powerset(idx+1);
		
		sel[idx] = false;
		powerset(idx+1);
	}

}

❗ 결과가 15개처럼 보이지만 맨 아래 공백(공집합)이 하나 더 있다.

---

📌 조합

🔷 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것

• 재귀로 표현하면 쉽다.
• nCr = n-1Cr-1 + n-1Cr, nC0 = 1

💡 서로 다른 5개의 재료 중 2개를 뽑아 만드는 경우의 수

import java.util.Arrays;

public class DailyClass {
	public static String[] 재료 = {"상추", "패티", "토마토", "치즈", "새우"};
	public static int N = 5;
	public static int R = 2; // 문제에서 판단할 수 있는 부분들
	public static String [] sel = new String[R]; // 내가 선택한 토핑
	
	public static void main(String[] args) {
		combination(0, 0);
	}

	// idx: 토핑의 index
	// sidx: sel의 index
	public static void combination(int idx, int sidx) {
		// 기저파트
		if(sidx == R) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		if(idx == N) return;
		
		// 재귀파트
		sel[sidx] = 재료[idx];
		combination(idx+1, sidx+1); // idx번째 재료를 뽑은 경우
		combination(idx+1, sidx); // idx번째 재료를 뽑지 않은 경우
	}
}

💡 같은 문제를 재귀 함수 내의 반복을 통해 풀 수도 있다.

import java.util.Arrays;

public class DailyClass {
	public static String[] 재료 = {"상추", "패티", "토마토", "치즈", "새우"};
	public static int N = 5;
	public static int R = 2; // 문제에서 판단할 수 있는 부분들
	public static String [] sel = new String[R]; // 내가 선택한 토핑
	
	public static void main(String[] args) {
		combination(0, 0);
	}

	// idx: 토핑의 index
	// sidx: sel의 index
	public static void combination(int idx, int sidx) {
		// 기저파트
		if(sidx == R) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		for(int i = idx; i <= N-R+sidx; i++) {
			sel[sidx] = 재료[i];
			combination(i+1, sidx+1);
		}
	}
}

결과는 같다.