如何理解这个递归

问题描述：

你好，我想了解这个解决方案组合总和。如何理解这个递归

function combinationSum(candidates, target) { 
    var result = []; 

    if ((candidates == null) || (candidates.length == 0)) { 
     return result; 
    } 

    var cur = []; 
    candidates = candidates.sort((a, b) => a - b) 
    csh(candidates, target, cur, result, 0); 

    return result; 
}; 

function csh(cand, target, cur, result, j) { 
    //console.log(cur); 
    if (target == 0) { 
     var temp = cur.slice(); 
     result.push(temp); 
     return; 
    } 

    for (var i = j; i < cand.length; i++) { 
     if (target < cand[i]) { 
      return; 
     } 

     //console.log(cur); 
     cur.push(cand[i]); 
     console.log(cur); 
     csh(cand, target - cand[i], cur, result, i); 
     cur.pop(); 
    } 
}

https://leetcode.com/problems/combination-sum/description/

虽然我理解递归的基本原则，这个问题是失去了我一点点。因此，例如，对于输入：

candidates = [2,3,6,7] 
target = 7

当你第一次进入该功能cur是空的，所以我们的第一次迭代是：

[], 
[2], 
[2,2]

然后我们不断增加cand[i]这是目前2

[2,2,2]

但是此时target = 1小于cand[i]这就是2所以我们回来。而且由于我们正在返回，我们弹出堆栈，弹出最后一个2。既然我们已经回到我们增加i，然后我们添加3到cur

[2,2,3]

因为我们的目标数组等于0我们现在再次返回，我的问题是，在这一点上我们的回头率，直到cur是空的并继续像下面的功能？

[2,2] 
[2] 
[] 
[6] 
[] 
[7]

我只是想了解这个功能正在做什么。

答

target是每个函数调用的局部。 target仅适用于函数的一些调用0。请注意，递归调用是：

csh(cand, target - cand[i], cur, result, i);

在该范围内还没有改变target，但csh当前正在输入将有其target较低值的调用。当该函数返回并且程序流程重新进入其他级别时，我们继续使用较高的值target，该值被提供给subcall的减少值target - cand[i]。

该算法将在[2,2,...]路径上尝试所有其他可能性，然后将第二个元素更改为下一个替代方法。然后它将探索[2,3,...]空间，以及[2,6,...]空间，最终还将探索所有[3,...],[6,...]和[7,...]的可能性。

算法总是尽可能地深入到尽可能深的地方（即尽可能长的数组），只要它不会超过原始限制即可。

注意，它不会产生[2,3,2]，因为先前的候选人不能在以后相继来（因此2永远不能在结果随后到3）。它通过使for的外观开始于i = j来强制执行此操作，其中j是所使用的最后一个候选的阵列深度，所以当进行中的结果以第012候选者结束时，它只考虑n th和更高的候选。这具有实际价值，因为该算法仅返回每个值结果集的一个置换：[2,2,3]和[2,3,2]包含相同的一组值。

啊好吧我想我知道你的意思，所以它做了类似[2]，[2,2]，[2,2,2]，pop（）现在[2,2,3]，现在弹出[2,2,6]然后弹出现在[2,2,7]然后[3]，[3,3]。[3,6]，[3,7]？ – motioncity

@motioncity除了'[2,2，...]'之外，它基本上是正确的，它将完成'[2,3，..]'，'[2,6，...]'和[ 2,7，...]'之前'[3，...]' – apsillers

答

我完全理解递归可能很难理解和解释，但这是我的承担。

当Csh为所要求的第一时间，这就是被传递

CSH（CAND，7，[]，[]，0）
从for循环
现在，i = 0，函数调用是

CSH（CAND，5，[2]，[]，0）
从环路，i = 0，函数调用是

CSH（CAND，3，[2,2]，[]，0）
从环路，i = 0，函数调用是

CSH（CAND，1，[2,2， 2]，[]，0）
从for循环中，target(1) < cand[0](2)，所以返回到步骤步骤4和从弹出最后2 [2,2,2]导致[2,2]
来自循环i = 1的
，调用的函数是

CSH（CAND，0，[2,2,3]，[]，1）
这里，target == 0条件成立。因此，[2,2,3]被推入结果中。然后再次返回步骤4. 3从[2,2,3]弹出。
从循环i = 2，target(3) < cand[2](6)，因此返回到步骤3，并从[2,2]中弹出2导致[2]。
从环路i = 1，函数调用是

CSH（CAND，2，[2,3]，[[2,2,3]，1）
从环路i = 1， target(2) < cand[1](1)所以返回到步骤9。

等没有...

基本上，每一种组合将被检查。

[2,2,2] 
[2,2,3] --> added to result 
[2,3,3] 
[2,6] 
[2,7] 
[3,3,3] 
[3,6] 
[3,7] 
[6,6] 
[6,7] 
[7] --> added to res

我喜欢解释！但我认为它应该是[2,2,2]的第一个电话。 – motioncity

@motioncity：是的，你是对的，我会更新我的解释 –

如何理解这个递归

相关推荐