[2017.12.27] 25. Recursion와 멱집합(PowerSet)

도입

이번 포스팅에서는 지난 포스팅 배웠던 Recursion을 이용해 집합의 멱집합(PowerSet)를 구하는 방법을 실습할 예정이다.

멱집합(PowerSet)의 개념

멱집합(PowerSet)은 대상집합의 모든 부분 집합이다. 예를 들어, 

대상 집합: {1,2,3}

멱집합 : 공집합, ,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

이다.

실습

Step1. 멱집합(PowerSet)을 구하기 위한 Thinking

Recursion을 사용하므로 공통된 작은 문제로 생각하면

첫 번째 원소 포함   (O)     + 첫 번째 원소를 제외한 나머지의 모든 부분집합

첫 번째 원소 미포함(X)     + 첫 번째 원소를 제외한 나머지의 모든 부분집합

그래서 인자로서 True/False를 입력 받아 해당 원소의 포함 여부를 결정하려 했다.

if (isInclude) {
    System.out.print(data[start]);
}
 
// 재귀  
myPowerSet(start+1, end, data, true);
myPowerSet(start+1, end, data, false);

그러나, 문제는 포함/미포함 되는 원소가 한번밖에 출력되지 않는다는 문제점이 있다.

그리고 근본적으로 중복으로 출력해야하는 값이 존재하는데 원소를 한개씩 출력해 처리할 수 있을까라는 생각이 들었다.

해결책

Step1. 원소의 포함 여부를 알 수 있는 boolean 배열 선언

private static boolean[] include = new boolean[n];

Step2. boolean 배열에 따라 출력 결정 

if (depth == n) {        
    for (int i=0; i<n; i=i+1) {
        // 포함 여부에 따라 출력 
        if (include[i])
            System.out.print(data[i]);
 
        System.out.println();
        return;
    }
}

결과

코드	스크린 샷
private static void powerSet(int depth) { // End Condition if (depth == n) { for (int i=0; i<n; i=i+1) { // 포함 여부에 따라 출력 if (include[i]) System.out.print(data[i]); } System.out.println(); return; } else { include[depth] = true; powerSet(depth+1); include[depth] = false; powerSet(depth+1); } }

#Recursion #멱집합 #java