부분집합(Subset)

🔹 부분집합이란 ?

• 한 집합의 원소들로만 구성한 집합을 말한다.
  • 집합의 원소가 총 n개일 때, 공집합을 포함한 부분집합의 개수는 2^n개다.
  • 즉, 각각의 원소들을 부분집합에 포함시키거나 포함하지 않는 두 가지의 경우를 모든 원소에 적용한 것의 경우의 수와 같다.

 

🔹 재귀를 이용한 구현

재귀를 이용하여 부분집합을 구현할 때는

• 현재 인덱스를 포함하는 경우
• 현재 인덱스를 포함하지 않는 경우

두 가지의 경우에 대해 모두 확인한 후 현재 인덱스가 n이 되었을 때 출력한다.

 

💭 Java  Code

public class Main {
	public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int n = 3;
        boolean[] checked = new boolean[n];

        subset(arr, checked, n, 0);
    }
    
    private static void subset(int[] arr, boolean[] checked, int n, int idx) {
        if (idx == n) { // 모든 인덱스를 다 탐색했다면
            for (int i = 0; i < n; i++) {
                if (checked[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        // 현재 인덱스 포함
        checked[idx] = true;
        subset(arr, checked, n, idx+1);
        // 현재 인덱스 포함 안함
        checked[idx] = false;
        subset(arr, checked, n, idx+1);
    }
}

 

 

📍 함께 풀어보면 좋은 백준 문제

• 15661 링크와 스타트
• 2961 도영이가 만든 맛있는 음식