JavaScriptで合計がnになるm個の数値の組み合わせを生成する方法

問題の概要

1から9までの数字のみを使い、重複のない組み合わせの中から、m個の数字を合計するとちょうどnになるすべての組み合わせを求める関数を作成します。各組み合わせ内で同じ数字を複数回使うことはできません。

たとえば、入力が次の場合：

const m = 3, n = 9;

出力は次のようになります。

const output = [
  [1, 2, 6],
  [1, 3, 5],
  [2, 3, 4]
];

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

この種の問題は、再帰的な深さ優先探索（バックトラッキング）を使うと効率的に解けます。各ステップで「現在の数字を採用する」「採用しない」という2つの分岐を試し、残り必要な個数と残りの目標合計がどちらも0になった時点で、その組み合わせを結果リストに追加します。数字を常に昇順で追加していくため、同じ内容の組み合わせが重複して生成されることはありません。

実装コード

const m = 3, n = 9;
const findSum = (m, n) => {
  const search = (from, prefix, m, n) => {
    // 必要な個数も合計も使い切ったら、完成した組み合わせを保存
    if (m === 0 && n === 0) return res.push(prefix);
    // 候補が9を超えたら探索終了
    if (from > 9) return;
    // 現在の数字「from」を採用する場合
    search(from + 1, prefix.concat(from), m - 1, n - from);
    // 採用しない場合
    search(from + 1, prefix, m, n);
  };
  const res = [];
  search(1, [], m, n);
  return res;
};
console.log(findSum(m, n));

コードのポイント

• search関数の引数：「from」は次に検討する候補の数字、「prefix」は現在構築中の組み合わせ、「m」はまだ必要な個数、「n」は残りの目標合計です。
• 終了条件：残り個数mと残り合計nが両方0になったとき、prefixは有効な解なので配列resに格納されます。
• 枝刈り：fromが9を超えたら候補が尽きたため、それ以上の探索を打ち切ります。
• 全列挙の仕組み：各数字について「採用する」と「採用しない」の両経路を再帰的に辿ることで、条件を満たすすべての組み合わせを漏れなく列挙できます。

出力結果

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

[ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 2, 3, 4 ] ]