JavaScriptで配列内の数値の組み合わせから目標値になる合計をすべて見つける方法

はじめに

本記事では、数値の配列と目標となる合計値を受け取り、その合計値を作り出せる数値の組み合わせをすべて見つけるJavaScript関数の作成方法を解説します。

要件

作成する関数は、以下のように動作する必要があります。

• 第1引数として数値の配列を受け取る
• 第2引数として単一の数値(目標合計値)を受け取る
• 配列から要素を選び、それらを加算したときに第2引数で指定された合計になる組み合わせを探す
• 条件を満たすすべての部分配列を含む配列を返す

なお、要素の順序は問わず、必要であれば同じ数値を複数回使用することも許容されます。

入力例

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

const arr = [14, 6, 10];
const sum = 40;

この場合、期待される出力は次のとおりです。

const output = [
    [ 14, 14, 6, 6 ],
    [ 14, 6, 10, 10 ],
    [ 6, 6, 6, 6, 6, 10 ],
    [ 10, 10, 10, 10 ]
];

実装方法：再帰による探索

この種の問題は、バックトラッキング(深さ優先探索)を用いた再帰処理で効率的に解くことができます。各要素について「その要素を選ぶ」か「選ばない」の2つの分岐を試し、部分和が目標値に達した時点で結果に追加していきます。

実際のコードは以下のとおりです。

const arr = [14, 6, 10];
const sum = 40;
const findSum = (arr, sum) => {
    const res = [];
    const search = (index, part = []) => {
        const s = part.reduce((a, b) => a + b, 0);
        if (s === sum){
            res.push(part)
        };
        if (s >= sum || index >= arr.length){ return; };
        search(index, part.concat(arr[index]));
        search(index + 1, part);
    };
    search(0);
    return res;
}
console.log(findSum(arr, sum));

コードの解説

• search関数:現在注目しているインデックスと、そこまでに選んだ要素の配列(part)を引数に取ります。
• reduce:part内の要素の合計値 s を計算します。
• s === sum の場合:合計が目標値と一致したため、partを結果配列 res に追加します。
• s >= sum または index >= arr.length の場合:これ以上探索しても意味がないため、再帰を終了します。
• search(index, part.concat(arr[index])):現在の要素を選ぶケースです。同じ要素を何度でも使えるようにするため、インデックスは進めません。
• search(index + 1, part):現在の要素を選ばないケースです。次の要素へ進みます。

出力結果

上記のコードを実行すると、コンソールには以下が出力されます。

[
    [ 14, 14, 6, 6 ],
    [ 14, 6, 10, 10 ],
    [ 6, 6, 6, 6, 6, 10 ],
    [ 10, 10, 10, 10 ]
]

このように、再帰的な探索を活用することで、重複使用を許可しながら目標の合計値を満たすすべての組み合わせを網羅的に求めることができます。