[Math] 부분집합과 멱집합 / Java

부분집합(Subset)과 멱집합(Power Set)

집합 A와 B가 있을 때, B의 특정 원소 x가 반드시 A의 원소이면 B를 A의 부분집합이라고 합니다.

그리고 이러한 부분집합(Subset)의 모든 경우의 수로 구성된 집합을 멱집합이라고 합니다.

부분집합을 Power Set으로 부르는 경우가 있는데 엄밀히 따지면 부분집합과 멱집합은 구분되는 개념입니다.

 

구현

구현 방식은 다음 두 가지가 있습니다.

1. 재귀와 방문배열을 활용한 방식
2. 비트마스킹을 활용한 방식

Java Code

public class PowerSet {

    static int[] arr = {1, 2, 3};
    static int n = arr.length;  // 주어진 수의 갯수
    static boolean[] visited = new boolean[n];  // 현재 조합에 특정 값이 포함되었는지 여부

    public static void main(String[] args) {
        powerSet(0);
//        powerSetWithBit();
    }

    // 1. 재귀와 방문배열을 활용한 구현
    static void powerSet(int depth) {
        if (depth == n) {
            print();
            return;
        }

        visited[depth] = true;
        powerSet(depth+1);

        visited[depth] = false;
        powerSet(depth+1);
    }

    // 2. 비트마스킹을 활용한 구현
    static void powerSetWithBit() {
        for (int i = 0; i < (1<<n); i++) {
            for (int j = 0; j < n; j++) {
                if ((i & (1<<j)) != 0) {
                    System.out.print(arr[j] + " ");
                }
            }
            System.out.println();
        }
    }

    static void print() {
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                System.out.print(arr[i]+ " ");
            }
        }
        System.out.println();
    }

}

 

실행결과는 다음과 같습니다.

1 2 3 
2 3 
1 3 
3 
1 2 
2 
1