有人可以向我解释一下canSum吗

Question

问题指出：

编写一个函数

canSum(targetSum, numbers)

，它接受

targetSum

和一个数字数组作为参数。该函数应返回一个布尔值，指示是否可以使用数组中的数字生成

targetSum

。您可以根据需要多次使用数组的元素。您可以假设所有数字都是非负数。

在我正在观看的动态规划视频中，解决方案是：

const canSum = (targetSum, numbers) => {
  if (targetSum === 0) return true;
  if (targetSum < 0) return false;

  for (let num of numbers) {
    const remainder = targetSum - num;
    if (canSum(remainder, numbers) === true) {
      return true;
    }
  }

  return false;
}

我理解这段代码如何在许多场景中工作，比如

canSum(7, [2, 3])

。但是我不明白这篇文章：

if (targetSum === 0) return true;

这意味着

canSum(0, [2, 3])

将导致true。根据问题，这不是该代码应该如何工作的。我在这里缺少什么？

谢谢你

console.log(canSum(7, [2, 4]))

结果为假

然而

console.log(canSum(0, [2]))

结果为真

Answer 1

当它说您可以根据需要多次使用任何数字时，这包括使用所有数字零次，当您这样做时，总和为

0

。使用它作为递归的基本情况可以简化算法，因为您只需不断减法，直到得到

0

。

另一种方法是使用

numbers.includes(targetSum)

作为基本情况。它们是等价的，因为当这是 true 时，

for

循环的迭代之一会将

remainder

设置为

0

，并且递归调用将具有

targetSum === 0

。

Answer 2

这里有两种执行 canSum 的方法

1 递归 // 求和

// recursion
// time => O(n^m)
// space => O(m)
//  n is length of array , m is number

const canSum = (numbers, targetsum) => {
  if (targetsum === 0) return true;
  if (targetsum < 0) return false;

  for (let num of numbers) {
    if (canSum(numbers, targetsum - num) === true) return true;
  }

  return false;
};

2 通过记忆

// V2 more optimized cause returns true if found any possible sum
//
// time => O(n* m)
// space => O(m)

const meoizeCanSumV2 = (numbers, targetsum, memo = {}) => {
  if (targetsum in memo) return memo[targetsum];
  if (targetsum === 0) return true;
  if (targetsum < 0) return false;

  for (let num of numbers) {
    const remainder = targetsum - num;
    if (meoizeCanSumV2(numbers, remainder, memo) === true) {
      memo[targetsum] = true;
      return true;
    }
  }

  memo[targetsum] = false;
  return false;
};

console.log(meoizeCanSumV2([3, 4, 7], 7));
console.log(meoizeCanSumV2([5, 3, 4, 7], 7));