C++で配列のすべての部分集合（サブセット）の合計を求める方法

問題の概要

整数の配列が与えられたとき、その部分集合（サブセット）から作り出せるすべての異なる合計値を求め、昇順に出力する方法を解説します。この問題は、配列の要素の合計値が比較的小さい場合に、動的計画法を使って効率的に解くことができます。

例として、配列 [1, 2, 3] を考えてみましょう。考えられるすべての部分集合は {}、{1}、{2}、{3}、{1, 2}、{2, 3}、{1, 3}、{1, 2, 3} であり、それぞれの合計値は 0, 1, 2, 3, 3, 5, 4, 6 となります。重複する値を取り除くと、出力は 0, 1, 2, 3, 4, 5, 6 となります。

アプローチ：動的計画法（DP）

この問題は動的計画法を用いて解きます。与えられた要素の合計が小さい場合、次のようなDPテーブルを作成します。

• 行のサイズ：配列の要素数（n+1）
• 列のサイズ：配列の全要素の合計値（sum+1）

テーブルの各セル table[i][j] は、「最初の i 個の要素を使って合計 j を作れるかどうか」を表します。要素を1つずつ追加しながら、既に達成可能な合計値 j に対して、「その要素を使わない場合（table[i][j]）」と「その要素を加える場合（table[i][j + arr[i-1]]）」の2つを順に true に更新していきます。最終的に、最終行で true になっている列のインデックスが、作成可能なすべての合計値に対応します。

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));
    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;
                table[i][j + arr[i-1]] = true;
            }
        }
    }
    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)、空間計算量も O(n × sum) となります。ここで n は配列の要素数、sum は配列の全要素の合計値です。そのため、要素の合計値が小さい場合に特に有効な手法といえます。