부분집합 (Subset)

부분 집합

집합(배열)에 포함된 원소들을 선택하는 것이다. 0 또는 1 배낭 짐싸기(0 or 1 Knapsack) 문제 같은 것이 다수의 중요 알고리즘에서 최적의 부분 집합을 찾는 것이다. 부분 집합의 개수는 집합의 원소가 n개일 때 $2^n$개가 된다. (따라서 시간 복잡도도 $O(2^n)$이다.)

각 원소를 부분 집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용하기 때문이다. 따라서 원소의 개수인 N이 25이상이면 다른 알고리즘을 생각해 봐야 한다.

구현

int N;

/**
 * @param count N의 원소 중 count의 원소를 선택/ 비선택 하기 위한 인덱스
 * @param idx 선택한 원소를 selected 배열에 저장하기 위한 인덱스이면서 부분 집합의 개수
 */
static void generateSubset(int count, int len) {
    // 부분 집합이 완성되었을 때 처리 (기저 조건)
    if (count == N) {	}
    // 선택
    generateSubset(count + 1, len + 1);
    // 선택 X
    generateSubset(count + 1, len);
}

부분 집합 코드는 재귀를 통해 구현한다. 이때 재귀 함수 호출이 두 번 이루어지는데, len + 1을 하는 경우는 집합의 원소를 선택하는 경우, len 그대로 다음 재귀 호출을 하는 경우는 집합의 원소를 선택하지 않는 경우이다.

문제 예시: 부분 집합의 합

유한 개수의 정수로 이루어진 집합이 있을 때, 이 집합의 부분 집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는 지 알기 위해서는 완전 탐색 기법을 통해 집합의 모든 부분 집합을 생성 후 각 부분 집합의 합을 계산하면 된다.

int[] data = {1, 2, -3, 4, 5};

static void generateSubsetwithParam(int count, int sum, int choice) {
    if (count == N) {
        if (sum == target && choice != 0) {
            for (int i = 0; i < N; i++) {
                System.out.print(check[i] ? input[i] + " " : "X ");
            }
            System.out.println();
        }
        return;
    }

    // 선택
    check[count] = true;
    generateSubsetwithParam(count + 1, sum + data[count], choice + 1);

    // 선택 X
    check[count] = false;
    generateSubsetwithParam(count + 1, sum, choice);
}