JavaScriptで目標の合計値になる全ての組み合わせを数える方法

問題

一意な整数の配列 arr を第1引数に、目標の合計値（target）を第2引数として受け取るJavaScript関数を作成する必要があります。

この関数は、同じ数値の繰り返し使用を許可したうえで、合計が目標値になるすべての組み合わせの数を数え、その結果を返さなければなりません。

例えば、関数への入力が次のような場合を考えてみましょう。

const arr = [1, 2, 3];
const target = 4;

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

const output = 7;

出力の説明

これは、合計が4になる組み合わせが以下の7通り存在するためです。

(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

ここで重要なのは、順序が異なる並びは別々の組み合わせとしてカウントされるという点です。例えば (1, 1, 2)、(1, 2, 1)、(2, 1, 1) はそれぞれ独立した1つとして数えられます。

コード例

この問題は、再帰処理にメモ化（memoization）を組み合わせることで効率的に解けます。メモ化により、一度計算した部分問題の結果をキャッシュし、同じ計算を繰り返す無駄を省きます。

const arr = [1, 2, 3];
const target = 4;
const sumUpto = (nums = [], target = 1, map = {}) => {
   if (target === 0){
      return 1;
   };
   if (typeof map[target] != "undefined"){
      return map[target];
   };
   let res = 0;
   for (let i = 0; i<nums.length; i++) {
      if (target >= nums[i]){
         res += sumUpto(nums, target - nums[i], map);
      };
   };
   map[target] = res;
   return res;
};
console.log(sumUpto(arr, target));

コードの解説

• ベースケース： target が 0 になった場合、残りを埋める方法は「何も選ばない」の1通りだけなので、1 を返します。
• キャッシュの確認： map オブジェクトに既にその target の計算結果が保存されている場合は、再計算せずにキャッシュ済みの値を即座に返します。
• 再帰的な探索： 配列内の各数値について、target がその数値以上であれば、target からその数値を差し引いた値で自分自身を再帰的に呼び出し、結果を累積していきます。
• 結果の保存： 求まった結果を map[target] に記録してから返すことで、以降の同一の計算を高速化しています。

このアプローチにより、素朴な再帰では指数関数的な時間計算量になるケースでも、メモ化によって大幅に計算量を抑えることができます。

出力

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

7