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

问题描述

问题是在一个排序数组中找到所有唯一的组合，这些组合总和为给定的目标值。对于此示例，假设候选人=[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] 等。

编辑：真的很晚了，我在原来的帖子中意识到我正在寻找一个不同的目标值，这增加了我的困惑......我修复了我的帖子以反映这一点。对不起！！

标签： javascriptcombinations

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

预赛

递归是基于这样的思想，即在增量构建组合的任何步骤，总和为一个目标，原始问题需要解决原始目标与使用相同集合的当前部分组合之和的差异的候选人。

参数combSum携带如下含义：

candidates：要从中选择的数字池（有序数组）
target：要组成的数字（整数）
current：当前正在完成的部分组合（有序数组）
result：到目前为止发现的组合
（伪字典顺序数组 - 前缀出现在它们的延续之后）
idxcandidates：要在调用中使用的元素的最小索引。

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

递归中有两个不变量：

表示当前正在完成的部分构造组合的数组中的元素current是非递减的。
序列是从左到右构建的。
特别是，没有递归调用会更改current调用时存在的元素。

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

请注意，这仅candidates在结果组合中没有出现重复的数字时才有效，否则将以该数字开头的子序列将被计算多次，从而产生几个相同的结果（ Try combinationSum([1,4], 4)and 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()恢复当前调用combSum开始的部分组合。这就是它的目的。虽然从技术上讲pop返回了一些值，但是这个值已经被使用了——它是current递归调用位置的顶部元素！

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

问题描述

解决方案

推荐阅读