在 JavaScript 中添加到目标的任何可能组合

Z时代
2024-01-10
分类：综合

问题

我们需要编写一个 JavaScript 函数，它接受一个唯一整数数组，arr 作为第一个参数，目标 sum 作为第二个参数。

我们的函数应该计算可以加起来为目标总和的所有对的数量（允许重复）并返回该计数。

例如，如果函数的输入是 -

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

那么输出应该是 -

const output = 7;

输出说明：

因为，可能的组合方式是 -

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

示例

此代码将是 -

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));