C++로 배열의 모든 고유한 부분 집합 합 구하기 – 동적 계획법(DP) 풀이

문제 정의

정수 배열이 하나 주어집니다. 이 배열의 부분 집합(subset)으로 만들 수 있는 모든 고유한 합(distinct sum)을 구한 뒤, 오름차순으로 출력하는 것이 목표입니다. 단, 배열 원소들의 총합은 작다고 가정합니다.

예를 들어 배열이 [1, 2, 3]일 때 가능한 부분 집합은 {}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}이며, 각각의 합은 순서대로 0, 1, 2, 3, 3, 5, 4, 6입니다. 여기서 중복된 값(3)을 하나로 묶고 정렬하면 최종 출력은 0, 1, 2, 3, 4, 5, 6이 됩니다.

풀이 접근: 동적 계획법(DP)

이 문제는 동적 계획법(Dynamic Programming)으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 배열 원소의 총합이 작으므로, 행의 개수가 배열 크기(n+1), 열의 개수가 원소 총합(sum+1)인 2차원 DP 테이블을 생성합니다.
• table[i][j]는 "앞의 i개 원소만 사용해서 합 j를 만들 수 있는가?"를 의미합니다.
• 어떤 원소도 고르지 않으면(공집합) 항상 합 0을 만들 수 있으므로 table[i][0] = true로 초기화합니다.
• table[i-1][j]가 참이라면, i번째 원소를 포함하지 않는 경우(table[i][j])와 포함하는 경우(table[i][j + arr[i-1]])가 모두 참이 됩니다.
• 탐색이 끝나면 마지막 행 table[n][j]가 참인 모든 j를 차례로 출력하면 됩니다. 열 인덱스가 곧 합의 값이므로, 별도의 정렬 없이도 자연스럽게 오름차순 결과를 얻을 수 있습니다.

C++ 구현 예제

#include<iostream>
#include<cstring>
using namespace std;

void displaySubsetSum(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];

    bool table[n + 1][sum + 1];
    memset(table, 0, sizeof(table));

    // 공집합으로 합 0은 항상 만들 수 있음
    for (int i = 0; i <= n; i++)
        table[i][0] = true;

    for (int i = 1; i <= n; i++) {
        table[i][arr[i - 1]] = true;
        for (int j = 1; j <= sum; j++) {
            if (table[i - 1][j] == true) {
                table[i][j] = true;              // i번째 원소 미포함
                table[i][j + arr[i - 1]] = true; // i번째 원소 포함
            }
        }
    }

    for (int j = 0; j <= sum; j++)
        if (table[n][j] == true)
            cout << j << " ";
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    displaySubsetSum(arr, n);
}

실행 결과

0 1 2 3 4 5 6

복잡도 분석

시간 복잡도와 공간 복잡도는 모두 O(n × sum)입니다. 여기서 n은 배열의 크기, sum은 배열 원소의 총합입니다. 원소 총합이 작은 입력에서 특히 효율적으로 동작하며, 필요에 따라 bitset 등을 활용하면 메모리 사용량을 더 줄일 수 있습니다.