【JavaScript】数値の再利用を許可して、目標の合計値に到達できるすべての組み合わせを生成する方法

はじめに

本記事では、JavaScriptを使って「配列内の数値を組み合わせて、目標の合計値（ターゲットサム）に到達するすべての組み合わせ」を求める方法を解説します。ポイントは、同じ数値を何度でも再利用できるという点です。これは典型的なバックトラッキング（探索の巻き戻し）を用いた再帰処理の応用例であり、アルゴリズムの学習にも最適な題材です。

要件の確認

まず、実装するJavaScript関数の仕様を整理しましょう。

• 第1引数として数値の配列、第2引数として目標となる合計値を受け取る
• 元の配列から要素を選び、その合計が目標値と一致するすべての部分配列を返す
• 1つの数値は複数回使用してよい

たとえば、入力が以下の場合を見てみましょう。

const arr = [1, 2, 4];
const sum = 4;

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

const output = [
    [1, 1, 1, 1],
    [1, 1, 2],
    [2, 2],
    [4]
]

ご覧のとおり、「4」そのものだけでなく、1や2を繰り返し使って合計4を作るパターンもすべて含まれています。

コード例

それでは、実際のコードを見ていきましょう。再帰的なバックトラッキングを使うことで、簡潔に実装できます。

const arr = [1, 2, 4];
const sum = 4;

const getCombinations = (arr = [], sum) => {
    const result = [];
    const pushElement = (i, t) => {
        // 現在の部分配列の合計を計算
        const s = t.reduce(function (a, b) {
            return a + b;
        }, 0);

        // 合計が目標値と一致したら結果に追加
        if (sum === s) {
            result.push(t);
            return;
        }

        // 合計が目標値を超えた、または配列の末尾に達した場合は打ち切り
        if (s > sum || i === arr.length) {
            return;
        }

        // パターン1: 現在の要素 arr[i] をもう一度選ぶ（同じ要素を再利用）
        pushElement(i, t.concat([arr[i]]));

        // パターン2: 次の要素へ進む
        pushElement(i + 1, t);
    }
    pushElement(0, []);
    return result;
};

console.log(getCombinations(arr, sum));

出力結果

コンソールには、次のように表示されます。

[ [ 1, 1, 1, 1 ], [ 1, 1, 2 ], [ 2, 2 ], [ 4 ] ]

アルゴリズムの解説

1. 再帰関数 pushElement の役割

内部関数 pushElement(i, t) は、「インデックス i 以降の要素を使って、現在の部分配列 t を伸ばすかどうかを決める」役割を担います。

2. 終了条件

• 部分配列の合計が目標値と一致 → 結果リストに追加して探索を終了
• 合計が目標値を超えた場合、あるいは配列の末尾まで到達した場合 → 無駄な探索を打ち切り（枝刈り）

3. 2つの分岐による全パターンの網羅

各ステップで次の2つの選択肢を再帰的に試します。

1. 同じ要素をもう一度選ぶ: pushElement(i, t.concat([arr[i]])) — インデックスを進めずに同じ要素を追加するため、数値の再利用が可能になります。
2. 次の要素に進む: pushElement(i + 1, t) — 部分配列はそのままに、候補を次の要素へ移します。

この2つの分岐を繰り返すことで、重複を含むすべての組み合わせを漏れなく生成できます。

まとめ

今回紹介したアプローチは、再帰とバックトラッキングを組み合わせることで、数値の再利用を許可した合計値マッチングの問題をエレガントに解決しています。同様の手法は「コイン両替問題」など、動的計画法や組み合わせ最適化の分野でも広く応用されており、ぜひマスターしておきたいテクニックです。