[Java]멱집합(Power Set)

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

 

예를 들어 A = {1, 2}라고 하면 A의 부분집합은 ∅(공집합), {1}, {2}, {1, 2}의 네 개다.

 

이때 A의 멱집합은 {∅, {1}, {2}, {1, 2}}가 된다.

 

n개의 원소를 가진 집합의 부분집합은 2^n 개이므로, 멱집합의 원소의 개수도 2^n개가 된다.

 

자바에서 멱집합을 구현할 때는 Stack과 재귀 함수를 이용하면 간단하게 작성할 수 있다.

import java.util.Stack;

public class PowerSet2 {

    public static void main(String[] args) {
        char[] characters = {'a', 'b', 'c'}; // 멱집합을 구할 집합
        Stack<Character> stack = new Stack<>(); // 부분집합을 저장할 스택
        search(stack, characters, 0);
    }

    private static void search(Stack<Character> stack, char[] characters, int k) {
        if(k >= characters.length) { // base case
            System.out.println(stack.toString());
        } else {
            stack.push(characters[k]); // k번째 요소를 부분집합에 포함
            search(stack, characters, k+1);

            stack.pop(); // k번째 요소를 부분집합에 포함하지 않음
            search(stack, characters, k+1);
        }
    }
}

search() 메서드를 사용해 k번째 인덱스가 될 때까지 재귀 호출을 한다.

 

위 상태 공간 트리에서 오른쪽 끝부터 탐색하는 코드이다.

 

트리구조의 레벨(k)이 집합의 길이(characters.length)와 같아지면 스택에 쌓인 집합을 출력한다고 보면 된다.