部分集合和問題（Subset Sum）とは？バックトラッキングによる解法をC++コード付きで解説

部分集合和問題（Subset Sum Problem）は、整数要素を含む集合が与えられたとき、その中から要素の合計が指定された値と一致する部分集合をすべて見つけ出す古典的なアルゴリズム問題です。

この問題の解法にはバックトラッキング（探索の巻き戻し）の手法が用いられます。候補となる要素を順番に部分集合へ追加していき、その要素が条件を満たさないと判断された時点で直前の状態に戻り、別の要素を試すことで効率的に解を探索します。

入力と出力

このアルゴリズムは、数値の集合と目標となる合計値を入力として受け取ります。以下は具体的な実行例です。

入力:
このアルゴリズムは数値の集合と合計値を受け取ります。
集合: {10, 7, 5, 18, 12, 20, 15}
合計値: 35

出力:
各部分集合の要素の合計が、与えられた合計値と一致するすべての部分集合。
{10, 7, 18}
{10, 5, 20}
{5, 18, 12}
{20, 15}

アルゴリズム

再帰関数のシグネチャは以下の通りです。

subsetSum(set, subset, n, subSize, total, node, sum)

入力 − 与えられた集合と部分集合、集合および部分集合のサイズ、部分集合の現在の合計値、部分集合内の要素数、そして目標の合計値。

出力 − 合計が目標値と一致するすべての部分集合。

処理の流れは次の擬似コードのようになります。

Begin
    if total = sum, then
        部分集合を表示する
        // 次の部分集合を探しに行く
        subsetSum(set, subset, , subSize-1, total-set[node], node+1, sum)
        return
    else
        for all element i in the set, do
            subset[subSize] := set[i]
            subSetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
        done
End

動作のポイント

• 現在の合計（total）が目標値（sum）に達したら、その時点の部分集合を出力します。
• その後、最後の要素を取り除いて合計を減らし、次のインデックスから探索を続けることで、重複のない別の組み合わせを探します。
• 合計が目標に達していない場合は、残りの要素を順に追加しながら再帰的に探索を深めていきます。

C++による実装例

#include <iostream>
using namespace std;

void displaySubset(int subSet[], int size) {
    for(int i = 0; i < size; i++) {
        cout << subSet[i] << "  ";
    }
    cout << endl;
}

void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount, int sum) {
    if( total == sum) {
        displaySubset(subSet, subSize);   // 部分集合を表示
        subsetSum(set, subSet, n, subSize-1, total-set[nodeCount], nodeCount+1, sum);   // 他の部分集合を探す
        return;
    } else {
        for( int i = nodeCount; i < n; i++ ) {   // 幅方向にノードを探索
            subSet[subSize] = set[i];
            subsetSum(set, subSet, n, subSize+1, total+set[i], i+1, sum);   // 深さ方向の次のノードへ進む
        }
    }
}

void findSubset(int set[], int size, int sum) {
    int *subSet = new int[size];   // subsetSum に渡す部分集合用の配列を作成
    subsetSum(set, subSet, size, 0, 0, 0, sum);
    delete[] subSet;
}

int main() {
    int weights[] = {10, 7, 5, 18, 12, 20, 15};
    int size = 7;
    findSubset(weights, size, 35);
}

出力結果

上記のコードを実行すると、合計が35になるすべての部分集合が以下のように出力されます。

10  7  18
10  5  20
5  18  12
20  15

計算量について

部分集合和問題は本質的にNP完全な問題であり、このバックトラッキングによる素朴な実装の最悪計算量は O(2ⁿ) となります。ただし、枝刈り（現在の合計がすでに目標値を超えたら探索を打ち切るなど）や、集合をあらかじめソートしておくことで、実際の探索範囲を大幅に削減できます。