バックトラッキング法で解く部分和問題（サブセットサム）のC/C++プログラム

バックトラッキング（Backtracking）は、探索型の問題を段階的に解決するための手法の一つです。解の候補を一歩ずつ構築していく過程で、その経路が解につながらないと判断した時点で、その経路を打ち切り、直前の分岐点へ戻って（バックトラックして）別の選択肢を試します。これにより、無駄な探索を大幅に減らすことができます。

「部分和問題（Subset Sum Problem）」は、この手法の代表的な応用例です。与えられた正の整数の集合の中から、要素の合計が指定された値 K と一致する部分集合をすべて見つけることを目標とします。ここでは、集合内の要素はすべて正の数であり、重複する要素は存在しないものとします。

この問題を解くには、考えられる部分集合を順次生成し、それぞれの合計が K と一致するかどうかを確認していきます。以下に、具体的な実装例を示します。

サンプルプログラム

#include <stdio.h>
#include <stdlib.h>
static int total_nodes;
void printValues(int A[], int size){
    for (int i = 0; i < size; i++) {
        printf("%*d", 5, A[i]);
    }
    printf("\n");
}
void subset_sum(int s[], int t[], int s_size, int t_size, int sum, int ite, int const target_sum){
    total_nodes++;
    if (target_sum == sum) {
        printValues(t, t_size);
        subset_sum(s, t, s_size, t_size - 1, sum - s[ite], ite + 1, target_sum);
        return;
    }
    else {
        for (int i = ite; i < s_size; i++) {
            t[t_size] = s[i];
            subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
        }
    }
}
void generateSubsets(int s[], int size, int target_sum){
    int* tuplet_vector = (int*)malloc(size * sizeof(int));
    subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
    free(tuplet_vector);
}
int main(){
    int set[] = { 5, 6, 12 , 54, 2 , 20 , 15 };
    int size = sizeof(set) / sizeof(set[0]);
    printf("The set is ");
    printValues(set , size);
    generateSubsets(set, size, 25);
    printf("Total Nodes generated %d\n", total_nodes);
    return 0;
}

実行結果

The set is 5 6 12 54 2 20 15
5 6 12 2
5 20
Total Nodes generated 127

プログラムのポイント

• subset_sum 関数：再帰呼び出しによって部分集合を1つずつ構築します。現在の合計が目標値に達した場合は、その部分集合を出力し、さらに残りの要素からなる別の解が存在しないか探索を続けます。
• generateSubsets 関数：探索に使用する一時的な配列（タプルベクトル）を malloc で確保し、再帰探索の起点となります。処理終了後にメモリを解放しています。
• total_nodes 変数：探索過程で訪れたノード（関数呼び出し）の総数を記録し、アルゴリズムの効率を評価する指標として利用しています。

上記の例では、集合 {5, 6, 12, 54, 2, 20, 15} の中から、合計が 25 になる部分集合として「5, 6, 12, 2」と「5, 20」の2通りが見つかりました。探索中に生成されたノードの総数は 127 個です。

なお、部分和問題を素朴な全探索で解いた場合、最悪で O(2ⁿ) の時間計算量が必要になります。そのため、「現在の合計が既に目標値を超えたら探索を打ち切る」といった枝刈りを追加することで、さらに高速化を図ることが可能です。