1 回答

TA貢獻(xiàn)1876條經(jīng)驗(yàn) 獲得超6個(gè)贊
該答案并未涉及可視化方面,而是僅限于您對(duì)特定細(xì)節(jié)的問(wèn)題。
預(yù)賽
遞歸基于這樣的思想,即在對(duì)目標(biāo)求和的組合的增量構(gòu)造中的任何一步,都需要針對(duì)原始目標(biāo)與使用相同集合的當(dāng)前部分組合之和的差異來(lái)解決原始問(wèn)題的候選人。
combSum
攜帶的參數(shù)含義如下:
candidates
:要從中挑選的數(shù)字池(有序數(shù)組)target
: 要組合的數(shù)字(整數(shù))current
: 當(dāng)前正在完成的部分組合(有序數(shù)組)result
:到目前為止發(fā)現(xiàn)的組合
(偽字典序排列的數(shù)組 - 前綴在它們的延續(xù)之后)idx
:candidates
要在調(diào)用中使用的元素的最小索引。
在概念上candidates
并idx
折疊成單個(gè)實(shí)參candidates.slice(i)
。
遞歸中有2個(gè)不變量:
current
表示當(dāng)前完成的部分構(gòu)造組合的數(shù)組中的元素是非遞減的。該序列是從左到右構(gòu)建的。
特別是,沒(méi)有遞歸調(diào)用會(huì)更改current
調(diào)用時(shí)存在的元素。
候選的排序有助于避免相同序列的重復(fù)構(gòu)造。請(qǐng)記住,在每次遞歸調(diào)用的有效候選元素是candidates.slice(i)
與i
非遞減,并在每個(gè)遞歸級(jí)別的循環(huán),這個(gè)層次的i
起始值開始與當(dāng)前值i
從父級(jí)。
請(qǐng)注意,這僅candidates
在結(jié)果組合中沒(méi)有出現(xiàn)重復(fù)數(shù)字時(shí)才有效,否則以該數(shù)字開頭的子序列將被多次計(jì)算產(chǎn)生幾個(gè)相同的結(jié)果( TrycombinationSum([1,4], 4)
和combinationSum([1,1,4], 4)
; 準(zhǔn)確地說(shuō),如果多重性incandidates
將等于每個(gè)結(jié)果的多重性......嘗試combinationSum([2,2,5], 9)
和combinationSum([2,5], 9)
)
1.遞歸基
遞歸基是這樣的n >= target
...
2. 跳過(guò)'不可能'前綴 ...如果n === target
,當(dāng)前部分組合完成并添加到結(jié)果中。如果n > target
當(dāng)前的部分組合不能成功完成(候選數(shù)字只會(huì)變大,當(dāng)前的已經(jīng)太大了)。但是,代碼不適合這種情況(它可以if (n > target) break;
在循環(huán)結(jié)束時(shí)使用語(yǔ)句)。
3.隱式返回 current.pop()
恢復(fù)combSum
started的當(dāng)前調(diào)用的部分組合。這是它的目的。雖然技術(shù)上pop
返回了一些值,但是這個(gè)值已經(jīng)被使用了——它是current
遞歸調(diào)用站點(diǎn)的頂部元素!
添加回答
舉報(bào)