如何理解這個遞歸

你好，我想了解這個解決方案組合總和。如何理解這個遞歸

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]

我只是想了解這個功能正在做什麼。

來源

2017-10-16 motioncity

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]包含相同的一組值。

來源

2017-10-16 18:37:43 apsillers

啊好吧我想我知道你的意思，所以它做了類似[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

來源

2017-10-16 22:34:54

我喜歡解釋！但我認爲它應該是[2,2,2]的第一個電話。 – motioncity

@motioncity：是的，你是對的，我會更新我的解釋 –

如何理解這個遞歸

回答

相關問題