백트래킹 - PowerSet

PowerSet

- n개의 원소를 가지는 배열의 모든 부분집합(2^n개)을 구하는 문제

조건

- n개의 원소의 부분집합은 총 2^n개

풀이전략

(1) n개의 배열의 각 원소가 부분집합에 포함되는지 여부를 나타내는 부분집합포함 배열 선언
   + 예를 들어 { 0, 1, 2, 3 } 의 부분집합 중 { 0, 2 } 를 부분집합포함 배열을 이용하여 나타내면 { 1, 0, 1, 0 } 이다

(2) 부분집합포함 배열의 인덱스를 0부터 3까지 증가시키면서 인덱스에 해당하는 원소를 포함하는 경우(1)와
    포함하지 않는 경우(0)을 각각 백트래킹을 실행한다. 

구현하기

 
/**
 * n개의 원소를 가지는 배열에서 모든 부분집합(2^n개)를 
 * 백트래킹 기법으로 구함
 * @author troh
 *
 */
public class Stack백트래킹_PowerSet {
    // n개의 원소를 가지는 배열
    private static int[] arr = {0, 1, 2, 3, 4};
    
    // arr의 각 인덱스가 부분집합에 포함되는지 0 또는 1로 표시하는 배열
    private static int[] inclusionArr = new int[arr.length];
    
    // 불포함, 포함 배열을 나타냄
    private static int[] candidates = {0, 1};
    
    public static void main(String[] args) {
        backTracking(inclusionArr, -1, inclusionArr.length-1);
    }
    
    /**
     * @param inclusionArr 부분집합포함 배열
     * @param incIndex inclusionArr의 인덱스
     * @param incLastIndex inclusionArr의 마지막
     */
    public static void backTracking(int[] inclusionArr, int incIndex, int incLastIndex) {
        // 부분집합포함 배열의 마지막까지 백트래킹이 실행되었다면 결과출력
        if(incIndex == incLastIndex) {
            System.out.printf("{");
            for(int i=0; i<inclusionArr.length; i++) {
                // 부분집합포함배열에 포함될 경우에만 원소를 출력
                if(inclusionArr[i] == 1) {
                    System.out.printf(" %d,", arr[i]);
                }
            }
            System.out.printf("}\n");
        } 
        else {
            // 부분집합포함 배열의 인덱스를 증가시킴
            incIndex++;
            
            // 해당 인덱스의 원소를 포함하는 경우와 포함하지않는 경우로 백트래킹 실행
            for(int i=0; i<candidates.length; i++) {
                inclusionArr[incIndex] = candidates[i];
                backTracking(inclusionArr, incIndex, incLastIndex);
            }
        }
    }
    
}
 

배운점..

음.. 뭐 저번에 NQueen문제를 백트래킹으로 구현하며 너무 삽질을 많이해서 이번 문제는 풀만하게 느껴진 것 같다. 그래도 백트래킹 기법에 대해 좀 더 이해할 수 있는 문제였다.