JavaScriptで解く！組み合わせ合計（Combination Sum）の問題とバックトラッキング実装

問題概要

重複のない候補数値（candidates）の集合と、目標値（target）が与えられているとします。

ここで求められるのは、候補数値の中から合計が目標値と一致するような、すべての一意な組み合わせを見つける関数を作成することです。

なお、同じ数値は候補の中から何度でも繰り返し選択できるものとします。

注意点

• すべての数値（target を含む）は正の整数であること。

• 解の集合には、重複した組み合わせを含めてはいけないこと。

例

入力が次の場合を考えてみましょう。

candidates = [2,3,6,7], target = 7,

このときの解は以下のようになります。

[
    [7],
    [2,2,3]
];

7 という単一の候補そのものも解になりますし、2 を二回と 3 を一回使った [2,2,3] も解として有効です。

アプローチ：再帰によるバックトラッキング

この問題は「最良の解」や「解の個数」ではなく、「考えられるすべての結果」を求めるものです。そのため動的計画法（DP）を検討する必要はなく、再帰を用いたバックトラッキングによるアプローチが適しています。

バックトラッキングの流れは以下の通りです。

• 候補となる数値を1つずつ現在の組み合わせに追加し、残りの合計を減らしながら再帰的に探索を進めます。

• 残りの合計がちょうど 0 になった時点で、その組み合わせを結果リストに保存します。

• 残りの合計が 0 未満（負）になった場合は、その経路を打ち切って前の状態へ戻ります。

• 再帰呼び出し時に開始インデックス（startFrom）を渡すことで、順序違いの重複した組み合わせが生成されるのを防いでいます。

コード例

以下が実装コードです。

const recursiveSum = (
    candidates,
    remainingSum,
    finalCombinations = [],
    currentCombination = [],
    startFrom = 0,
) => {
    if (remainingSum < 0) {
        return finalCombinations;
    }
    if (remainingSum === 0) {
        finalCombinations.push(currentCombination.slice());
        return finalCombinations;
    }
    for (let candidateIndex = startFrom; candidateIndex < candidates.length; candidateIndex += 1) {
        const currentCandidate = candidates[candidateIndex];
        currentCombination.push(currentCandidate);
        recursiveSum(
            candidates,
            remainingSum - currentCandidate,
            finalCombinations,
            currentCombination,
            candidateIndex,
        );
        currentCombination.pop();
    }
    return finalCombinations;
}
const combinationSum = (candidates, target) => recursiveSum(candidates, target);
console.log(combinationSum([2, 3, 6, 7], 7));

ポイントとしては、組み合わせを保存する際に currentCombination.slice() でコピーを作成している点です。これは配列を参照渡しすると、その後の pop() 操作によって保存済みの結果まで書き換えられてしまうためです。

出力結果

コンソールへの出力は以下の通りです。

[ [ 2, 2, 3 ], [ 7 ] ]

このように、再帰とバックトラッキングを組み合わせることで、候補数値の重複使用を許容しつつ、重複のない組み合わせをすべて効率的に列挙できます。