我在可视化组合和问题的递归调用时遇到了一些麻烦？

Question

问题是在排序数组中找到总和为给定目标值的所有唯一组合。在这个例子中，假设候选者=[2,3,6,7] 和目标=7。我看了一些视频，现在我了解了如何解决这个问题的一般算法。我还查看了一个解决方案，但是在可视化函数中的递归树/每个递归调用时遇到了一些麻烦。var combinationSum = function(candidates, target) {    candidates.sort((a,b) => a-b)    let result = []    combSum(candidates, target, [], result, 0)    return result };function combSum(candidates, target, current, result, idx) {    let n    for (let i = idx; i < candidates.length; i++) {        n = candidates[i]        current.push(n)        if (n === target) {            result.push([...current])        } else if (target > n) {             combSum(candidates, target-n, [...current], result, i)        }        current.pop()    } }我知道第一步是尝试从数组中的第一个值 2 开始的组合。所以函数将尝试 [2]，然后是 [2,2]，然后是 [2,2,2]，此时目标是小于 n 的 1，因此它跳过 if 语句并弹出最后 2 个。pop() 方法是否隐式返回调用堆栈上的前一个函数调用？它会返回一个从未实际使用过的值 2，这是正确的吗？没有让我失望的基本案例。另外，我知道由于数组已排序，我们应该知道如果像 [2,2,3,3] 这样的东西不起作用，那么以 [2,2,3] 前缀开头的任何其他组合也将起作用不行。我不明白代码是如何解决这个问题的——它怎么知道“跳过”这些组合？像 [2,2,3,6] 等。编辑：真的很晚了，我在我原来的帖子中意识到我正在寻找一个不同的目标值，这增加了我的困惑......我修复了我的帖子以反映这一点。对不起！！

Answer 1

该答案并未涉及可视化方面，而是仅限于您对特定细节的问题。

预赛

递归基于这样的思想，即在对目标求和的组合的增量构造中的任何一步，都需要针对原始目标与使用相同集合的当前部分组合之和的差异来解决原始问题的候选人。

combSum携带的参数含义如下：

• candidates：要从中挑选的数字池（有序数组）

• target: 要组合的数字（整数）

• current: 当前正在完成的部分组合（有序数组）

• result：到目前为止发现的组合
  （伪字典序排列的数组 - 前缀在它们的延续之后）

• idx:candidates要在调用中使用的元素的最小索引。

在概念上candidates并idx折叠成单个实参candidates.slice(i)。

递归中有2个不变量：

• current表示当前完成的部分构造组合的数组中的元素是非递减的。

• 该序列是从左到右构建的。
  特别是，没有递归调用会更改current调用时存在的元素。

候选的排序有助于避免相同序列的重复构造。请记住，在每次递归调用的有效候选元素是candidates.slice(i)与i非递减，并在每个递归级别的循环，这个层次的i起始值开始与当前值i从父级。

请注意，这仅candidates在结果组合中没有出现重复数字时才有效，否则以该数字开头的子序列将被多次计算产生几个相同的结果（ TrycombinationSum([1,4], 4)和combinationSum([1,1,4], 4); 准确地说，如果多重性incandidates将等于每个结果的多重性......尝试combinationSum([2,2,5], 9)和combinationSum([2,5], 9)）

1.递归基
递归基是这样的n >= target...

2. 跳过'不可能'前缀 ...如果n === target，当前部分组合完成并添加到结果中。如果n > target当前的部分组合不能成功完成（候选数字只会变大，当前的已经太大了）。但是，代码不适合这种情况（它可以if (n > target) break;在循环结束时使用语句）。

3.隐式返回 current.pop()恢复combSumstarted的当前调用的部分组合。这是它的目的。虽然技术上pop返回了一些值，但是这个值已经被使用了——它是current递归调用站点的顶部元素！