부분집합(Subset)

멱집합(PowerSet)의 수 = 2^n

 

아래는 부분집합을 구하는 알고리즘 문제이다.

 

1) 부분집합 * 순열(중복 순열 아님)

https://www.acmicpc.net/problem/15654

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int n, m;
	static int[] arr, selected;
	static boolean[] used;
	static StringBuilder sb;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
        
		arr = new int[n + 1];
		selected = new int[m + 1];
        
		int max = Integer.MIN_VALUE;
        
		for (int a = 1; a <= n; a++) {
			arr[a] = sc.nextInt();
			max = Math.max(max, arr[a]);
		}
		used = new boolean[max + 1];
		Arrays.sort(arr); // 정렬
		sb = new StringBuilder();
		rec(1);
		System.out.println(sb.toString());
		sc.close();
	}

	private static void rec(int idx) {
		// 기저조건
		if (idx == m + 1) {
			for (int s = 1; s <= m; s++) {
				sb.append(selected[s]).append(" ");
			}
			sb.append("\n");
			return;
		}

		// 유도조건
		for (int a = 1; a <= n; a++) {
			if (used[arr[a]]) { // 중복 불허
				continue;
                // 직전에 뽑은 수와 대소비교 하지 않음으로써 순서 반영 -> 순열
			}
			selected[idx] = arr[a];
			used[arr[a]] = true; // 방문처리
			rec(idx + 1);
			used[arr[a]] = false; // 방문처리 취소
		}
	}
}

 

2) 부분집합 * 조합(중복 조합 아님)

 

https://www.acmicpc.net/problem/15655

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int n, m;
	static int[] arr, selected;
	static StringBuilder sb;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();

		arr = new int[n + 1];
		selected = new int[m + 1];

		for (int a = 1; a <= n; a++) {
			arr[a] = sc.nextInt();
		}
		Arrays.sort(arr); // 정렬
		sb = new StringBuilder();
		rec(1);
		System.out.println(sb.toString());
		sc.close();
	}

	private static void rec(int idx) {
		// 기저 조건
		if (idx == m + 1) {
			for (int s = 1; s <= m; s++) {
				sb.append(selected[s]).append(" ");
			}
			sb.append("\n");
			return;
		}

		// 유도 조건
		for (int a = 1; a <= n; a++) {
			if (selected[idx - 1] < arr[a]) { // 직전의 수가 더 작은 경우에만
				selected[idx] = arr[a]; // 수를 뽑는다 -> 조합 
			} else { // 크거나 같으면 뽑지 않는다. 그래야 순서 반영하지 않음
				continue;
			}
			rec(idx + 1);
		}
	}
}