JavaScriptで配列の要素から目標の合計になるすべての組み合わせを求める方法

数値の配列を第1引数に、目標となる合計値を第2引数として受け取るJavaScript関数を作成する必要があります。この関数は、配列内の要素(同じ要素の繰り返し使用も可)を組み合わせて、合計が目標値と一致するすべての組み合わせを、配列の配列として返すものです。

問題の例

たとえば、入力配列が次のような場合を考えてみましょう。

const arr = [2, 3, 6, 7], sum = 7;

この入力に対する出力は、次のようになります。

const output = [
    [2, 2, 3],
    [7]
];

「2 + 2 + 3」と「7」の2通りの組み合わせが、いずれも合計7になるためです。

実装コード

この処理を実現するコードは次の通りです。

const arr = [2, 3, 6, 7], sum = 7;
const combineElements = (arr, sum) => {
    const output = [];
    const findCombination = (remain, path, start) => {
        if (remain < 0) {
            return;
        }
        if (remain === 0) {
            output.push([...path]);
            return;
        }
        for (let i = start; i < arr.length; i++) {
            findCombination(remain − arr[i], [...path, arr[i]], i);
        }
    }
    findCombination(sum, [], 0);
    return output;
};
console.log(combineElements(arr, sum));

アルゴリズムの解説

この実装では、バックトラッキング(深さ優先探索)と呼ばれる手法を使用しています。処理の流れは以下の通りです。

• findCombination関数は、「残りの必要な合計(remain)」「現在の組み合わせ(path)」「探索を開始するインデックス(start)」の3つの引数を受け取ります。
• remainが0未満になった場合は、組み合わせの合計が目標値を超えていることを意味するため、その経路の探索を打ち切ります。
• remainがちょうど0になった場合は、その組み合わせが条件を満たしているため、pathのコピーを結果配列に追加します。
• それ以外の場合は、start以降の各要素を組み合わせに追加しながら再帰的に探索を続けます。再帰呼び出し時に同じインデックスiを渡すことで、同一要素の繰り返し使用を許可しています。

実行結果

コンソールには次のように出力されます。

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