1 回答

TA貢獻1876條經驗 獲得超6個贊
該答案并未涉及可視化方面,而是僅限于您對特定細節的問題。
預賽
遞歸基于這樣的思想,即在對目標求和的組合的增量構造中的任何一步,都需要針對原始目標與使用相同集合的當前部分組合之和的差異來解決原始問題的候選人。
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()
恢復combSum
started的當前調用的部分組合。這是它的目的。雖然技術上pop
返回了一些值,但是這個值已經被使用了——它是current
遞歸調用站點的頂部元素!
添加回答
舉報