멱집합

public class PowerSet {
    private static char data[]= {'a','b','c','d'};
    private static int n=data.length;
    private static boolean[] include = new boolean[n];
    
    public static void powerSet(int k) {
        System.out.format("powerSet(%d) 호출됨.\n",k);
        if(n==k) {
            for(int i=0;i<n;i++) {
                if(include[i]) System.out.print(data[i]+" ");
            }
            System.out.println();
            return;
        }
        System.out.format("집합 %c 원소는 미포함한 부분집합 구하기 powerSet(%d)\n", data[k], k+1);
        include[k]=false;
        powerSet(k+1);
        System.out.format("집합 %c 원소를 포함시킨 부분집합 구하기 powerSet(%d)\n", data[k],k+1);
        include[k]=true;
        powerSet(k+1);
        
    }
    
    public static void printArray() {
        for(char c: data) {
            System.out.format("%c ",c);
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        powerSet(0);
    }
 
}

멱집합은 주어진 집합의 모든 부분 집합들로 구성된 집합이다.

모든 경우의 수를 구하는 순열은 구현할 수 있지만, 순서가 상관 없는 멱집합을 구하는데 어려움이 있었다.

이에 작동 방식을 잘 확인할 수 있는 코드를 가져왔다.

 

참고 사이트 : https://digest1.tistory.com/10