JavaScriptで＋と－の割り当てにより目標の合計になるパターン数を求める方法

問題

整数の配列 arr を第1引数に、単一の整数 target を第2引数として受け取る JavaScript 関数を作成する必要があります。

配列内の各整数に対して、「+」または「-」のどちらか一方を割り当てることができます。

この関数の目的は、配列内のすべての整数の合計が目標値 target と一致するように「+」と「-」を割り当てる方法が、合計で何通り存在するかを求めることです。

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

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

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

const output = 5;

出力の解説

答えが 5 になるのは、以下の 5 通りの割り当て方が存在するためです。

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

アルゴリズムの考え方

各要素に対して「+」と「-」の2択があるため、すべての組み合わせを素朴に試すと O(2ⁿ) の計算量が必要になり、配列が長くなると現実的ではありません。そこで有効なのが、再帰処理とメモ化（キャッシュ）を組み合わせたアプローチです。

実装のポイントは次のとおりです。

• 末尾の要素から順に処理し、残りの目標値に対して「その要素を足す場合」と「引く場合」の2通りに分岐しながら再帰的に探索します。
• 「インデックスと目標値のペア」をキーとしたオブジェクトに計算結果をキャッシュすることで、同じ状態を繰り返し計算する無駄を省き、計算量を大幅に削減できます。
• 先頭の要素まで到達したとき、目標値が 0 かつ先頭要素が 0 であれば「+0」と「-0」の2通りが成立するため 2 を返します。それ以外の場合は、先頭要素が目標値またはその符号反転と一致するときに 1 を返します。

コード例

実際のコードは次のようになります。

const arr = [1, 1, 1, 1, 1];
const target = 3;
const waysToSum = (arr = [], target = 1) => {
   const map = {};
   const find = (arr, target, i) => {
      let val = i + '->' + target;
      if(map[val] !== undefined){
         return map[val];
      };
      if(i === 0){
         if (target === 0 && arr[0] === 0) { return 2 }
         return arr[0] === target || arr[0] === -target ? 1 : 0
      };
      map[val] = find(arr, target + arr[i], i - 1) + find(arr, target - arr[i], i - 1);
      return map[val]
   };
   return find(arr, target, arr.length-1)
};
console.log(waysToSum(arr, target));

出力結果

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

5