부분 집합 문제

유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지 확인하는 알고리즘을 알아보겠습니다.

먼저 문제를 풀기 위한 절차는 아래와 같이 생각해볼 수 있습니다.

1.  완전 검색기법으로 모든 부분집합을 구하기
2.  부분집합을 모두 더해서 0과 일치하는지 확인해보기

전체적인 성능에 영향을 미치는 (1)번 절차의 알고리즘을 만들어보도록 하겠습니다.

1. 반복문을 이용한 부분집합 구하기

int[] arr = {1, 2, 3, 4}

1.  1이 부분집합에 포함되었을 경우와 안되었을 경우 ( 2가지 )
2.  2가 부분집합에 포함되었을 경우와 안되었을 경우 ( 2가지 )
3.  3이 부분집합에 포함되었을 경우와 안되었을 경우 ( 2가지 )
4.  4가 부분집합에 포함되었을 경우와 안되었을 경우 ( 2가지 )

위의 과정을 개발 코드로 구현해보도록 하겠습니다. bitArr은 인덱스 요소의 표현 여부를 정하는 비트(0, 1)을 저장하고 있습니다.  즉 bitArr[0]의 값이 1이면 arr[0]을 부분집합으로 가지는 것입니다.

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        int[] bitArr = new int[4];
        
        for(int i=0; i<2; i++) {
            bitArr[0] = i%2==0 ? 0:1;
            for(int j=0; j<2; j++) {
                bitArr[1] = j%2==0 ? 0:1;
                for(int k=0; k<2; k++) {
                    bitArr[2] = k%2==0 ? 0:1;
                    for(int l=0; l<2; l++) {
                        bitArr[3] = l%2==0 ? 0:1;
                        
                        for(int m=0; m<4; m++) {
                            if(bitArr[m] != 0 ) {
                                System.out.printf(arr[m]+", ");
                            }
                        }
                        System.out.println("");
                    }
                }
            }
        }
    }

위 코드를 이해하기 쉽게 그림으로 일부 표현해 보았습니다.  아래와 같이 진행한다면 네 번째 반복문에는 16개의 (0 0 0 0 ~ 1 1 1 1)의 bitArr 형태를 만들어 낼 것입니다. 각 배열에서 값이 1인 인덱스만 arr[인덱스] 로 출력하면 총 16개의 부분집합을 구할 수 있습니다. 

2. 비트연산자를 이용한 부분집합 구하기

비트연산자를 이용하여 부분집합을 구하기 전에 아래의 연산을 이해해야 합니다. 

1. 1 << n 은 원소가 n개일 경우 모든 부분집합의 수 
2. i & ( 1<< j )  은 i 의 j번째 인덱스가 0인지 1인지 확인가능

위에서 배운 bitArr ( 0 0 0 0 ~ 1 1 1 1 )을 정수형으로 변환하면 0~15입니다.  즉 0~ 15까지 반복하면서 각 인덱스의 자리가 1인지 0인지 판별하여 부분집합을 구하는 방법입니다. 1인지 0인지 판별하는 부분은 i & ( 1 << j ) 연산으로 수행합니다. 

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        
        for(int i=0; i<(1<<4); i++) {
            for(int j=0; j<4; j++) {
                if( (i & (1<<j)) >= 1) {
                    System.out.printf("%d, ", arr[j]);
                }
            }
            System.out.println("");
        }
    }