Leetcode2 組合總和、組合總和II、組合
今天了做了三道比較常規(guī)的遞歸+組合問題
組合總和：
數(shù)組中不存在重復(fù)元素，但是一個元素可以重復(fù)多次選擇。就像實(shí)例1中的 2 2 3一樣。
所以這道題的思路就是：
控制遞歸的時候從左向右遍歷數(shù)組
因?yàn)榭梢赃x擇重復(fù)的數(shù)字，所以在下次遞歸的時候還可以從當(dāng)前下標(biāo)嘗試一次
如果當(dāng)前值已經(jīng)超出了預(yù)期結(jié)果，直接return，說明這種嘗試失敗了。
具體的代碼如下：
組合總和II：
在數(shù)組中存在重復(fù)的數(shù)字，最后的結(jié)果中不能包括重復(fù)的策略。因此這道題有點(diǎn)像全排列II，在上面的代碼基礎(chǔ)上，我們將數(shù)組按照升序或者是降序進(jìn)行排列，還是需要保證從左向右進(jìn)行掃描。如果當(dāng)前遍歷到的下標(biāo)對應(yīng)的數(shù)字和前面一個相同，并且前面一個數(shù)字不在當(dāng)前的遞歸樹上，我們就可以繼續(xù)遞歸。在不在當(dāng)前的遞歸樹上，我們還是可以采用全排列II中的方法記錄。這里舉個例子：
在我們排序之后，我們會從左往右遍歷數(shù)組，不會試探重復(fù)的元素。因?yàn)槲覀冊谕顺鲞f歸的時候會恢復(fù)現(xiàn)場，所以在情況二中vis[j-1] = false，表明這種情況及其后續(xù)分值已經(jīng)被完成了，所以如果nums[j] == nums[j-1] 直接跳出。
這里我感覺在上篇文章中沒有解釋清楚，如果看到的小伙伴還是存在疑問的話可以私信我交流一下~
具體的代碼如下所示：
組合
使用遞歸的話有明顯的幾處可以進(jìn)行剪枝：
因?yàn)樯a(chǎn)的數(shù)組不能存在重復(fù)值，所以我們還是從左往右進(jìn)行掃描，然后掃描之后其實(shí)我們是在剩余的元素組成的數(shù)組中進(jìn)行挑選。考慮一種最壞的情況，剩余元素假設(shè)被選擇完，可以構(gòu)成K個數(shù)嗎？ 所以當(dāng)前選擇數(shù)字的個數(shù)和剩余數(shù)組的元素還有K三者存在一個關(guān)系，我們通過這個關(guān)系可以進(jìn)行剪枝：
具體代碼如下：
