1 題目描述

2? 解題思路?

• 如果解決一個(gè)問(wèn)題有多個(gè)步驟，每一個(gè)步驟有多種方法，題目又要我們找出所有的方法，可以使用回溯算法；
• 回溯算法是在一棵樹(shù)上的?深度優(yōu)先遍歷（因?yàn)橐宜械慕?#xff0c;所以需要遍歷）；
• 組合問(wèn)題，相對(duì)于排列問(wèn)題而言，不計(jì)較一個(gè)組合內(nèi)元素的順序性（即 [1, 2, 3] 與 [1, 3, 2] 認(rèn)為是同一個(gè)組合），因此很多時(shí)候需要按某種順序展開(kāi)搜索，這樣才能做到不重不漏。

既然是樹(shù)形問(wèn)題上的 深度優(yōu)先遍歷，因此首先畫(huà)出樹(shù)形結(jié)構(gòu)。

例如輸入：n = 4, k = 2，我們可以發(fā)現(xiàn)如下遞歸結(jié)構(gòu)：

如果組合里有 1 ，那么需要在 [2, 3, 4] 里再找 1個(gè)數(shù)；
如果組合里有 2 ，那么需要在 [3, 4] 里再找 1數(shù)。注意：這里不能再考慮 1，因?yàn)榘?1?的組合，在第 1 種情況中已經(jīng)包含。
依次類(lèi)推（后面部分省略），以上描述體現(xiàn)的 遞歸 結(jié)構(gòu)是：在以 n?結(jié)尾的候選數(shù)組里，選出若干個(gè)元素。畫(huà)出遞歸結(jié)構(gòu)如下圖：

參考：https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/

2.1? 未剪枝回溯

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:res = []def backtrace(i,tmp):if len(tmp) == k:res.append(tmp)returnfor j in range(i,n+1):backtrace(j+1,tmp+[j])backtrace(1,[])return res

這里backtrace(i,lst)的意思是：在[1,i)里面，我們已經(jīng)找到了一個(gè)排序lst（最后一個(gè)數(shù)就是i-1）。然后我們?cè)赱i,n]里面找一個(gè)點(diǎn)，作為排序的下一個(gè)點(diǎn)。

當(dāng)我們lst的長(zhǎng)度已經(jīng)是k的時(shí)候，滿(mǎn)足條件，就可以將這個(gè)序列放入我們要返回的部分了

這樣查找是不會(huì)有重復(fù)的序列的。

2.2 剪枝回溯

但是，上述方法會(huì)有很多地方存在冗余，當(dāng)我們剩余沒(méi)有查看的序列的長(zhǎng)度比我們還需要取得元素個(gè)數(shù)要少的時(shí)候，那么即使后面整個(gè)序列中的元素全部取出來(lái)，也不能達(dá)到條件。那么這一部分的backtrace就可以不用考慮了。

剪枝后的代碼如下：

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:res = []def backtrace(i,tmp):if len(tmp) == k:res.append(tmp)returnfor j in range(i,n+1):if(len(tmp)+n-j+1<k):returnbacktrace(j+1,tmp+[j])backtrace(1,[])return res

多了一句if(len(tmp)+n-j+1<k):，就是來(lái)判斷剩余序列的長(zhǎng)度是否滿(mǎn)足要求的

可以看到，時(shí)間復(fù)雜度小了很多

2.3 寫(xiě)代碼的時(shí)候的一個(gè)小坑

一開(kāi)始我是這么寫(xiě)的，然后報(bào)錯(cuò)了

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:tmp=[]ans=[]def dfs(idx):if(len(tmp)+(n-idx+1)<k):returnif(len(tmp)==k):ans.append(tmp)returntmp.append(idx)dfs(idx+1)tmp.pop()dfs(idx+1)dfs(1)return(ans)

?從邏輯上看，也沒(méi)有問(wèn)題，但是注意一點(diǎn)，就是append(tmp) append的是一個(gè)引用，所以append里面的值會(huì)是一樣的。

?

稍微修改一下，就對(duì)了

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:ans=[]def dfs(idx,tmp):if(len(tmp)+(n-idx+1)<k):returnif(len(tmp)==k):ans.append(tmp)returndfs(idx+1,tmp)tmp1=tmp+[idx]dfs(idx+1,tmp1)dfs(1,[])return(ans)

總結(jié)

以上是生活随笔為你收集整理的文巾解题 77. 组合的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。