멱집합 (부분집합 - Power Set) 알고리즘

멱집합 알고리즘

멱집합은 한 집합의 모든 부분집합을 뜻합니다. 원소 a,b,c를 갖고 있는 집합의 모든 부분 집합은 (a, b, c, ab, ac, bc, abc + 공집합)으로 총 8가지 입니다. 탐색 (재귀, 브루트포스) 알고리즘 문제를 풀때 멱집합을 구하는 방법을 종종 사용하게 됩니다.  

모든 부분집합의 경우의 수를 구하는 과정은 다음과 같습니다.

• 첫번째 원소가 포함이 되는가? 혹은 안되는가?
• → 두번째 원소가 포함이 되는가? 혹은 안되는가? 
• → . . . 
• → N번째 원소가 포함이 되는가? 혹은 안되는가? 

그래서 원소의 갯수가 N인 집합의 모든 부분집합의 갯수는 2^N개가 됩니다. 아래는 주어진 집합의 모든 부분집합을 출력하는 (java)코드입니다. 핵심부분은 위에서 설명한대로 n번째의 원소가 포함이 되는지 안되는지 2가지 경우를 모두 고려하고, 이 후의 과정은 재귀적으로 진행합니다. (코드 상 배열을 이용하기 떄문에 n은 0번째 부터 시작합니다.)

public class PowerSet {
    public static void main(String[] args) {
        char[] data = {'a', 'b', 'c'};
        int[] flag = new int[data.length];

        powerSet(data, flag, 0);
    }

    static void powerSet(char[] data, int[] flag, int n) {
        //종료조건 (기저사례)
        if (n == data.length) {
            //출력을 위한 메소드
            printData(data, flag);
            return;
        }

        //포함을 시키는 경우
        flag[n] = 1;
        powerSet(data, flag, depth + 1);

        //포함을 시키지 않는 경우
        flag[n] = 0;
        powerSet(data, flag, depth + 1);
    }

    static void printData(char[] data, int[] flag) {
        for (int i = 0; i < flag.length; i++) {
            if (flag[i] == 1) {
                System.out.print(data[i] + "\t");
            }
        }
        System.out.println();
    }
}

//실행 결과 (*공집합은 표시가 안됨)
a	b	c	
a	b	
a	c	
a	
b	c	
b	
c