一篇讓你學(xué)會(huì)組合問題！
組合
力扣題目鏈接：https://leetcode-cn.com/problems/combinations/
給定兩個(gè)整數(shù) n 和 k，返回 1 ... n 中所有可能的 k 個(gè)數(shù)的組合。
示例: 輸入: n = 4, k = 2 輸出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
本題這是回溯法的經(jīng)典題目。
直接的解法當(dāng)然是使用for循環(huán)，例如示例中k為2，很容易想到 用兩個(gè)for循環(huán)，這樣就可以輸出 和示例中一樣的結(jié)果。
代碼如下：
- int n = 4;
- for (int i = 1; i <= n; i++) {
- for (int j = i + 1; j <= n; j++) {
- cout << i << " " << j << endl;
- }
- }
輸入：n = 100, k = 3 那么就三層for循環(huán)，代碼如下：
- int n = 100;
- for (int i = 1; i <= n; i++) {
- for (int j = i + 1; j <= n; j++) {
- for (int u = j + 1; u <= n; n++) {
- cout << i << " " << j << " " << u << endl;
- }
- }
- }
如果n為100，k為50呢，那就50層for循環(huán)，是不是開始窒息。
此時(shí)就會(huì)發(fā)現(xiàn)雖然想暴力搜索，但是用for循環(huán)嵌套連暴力都寫不出來!
咋整?
回溯搜索法來了，雖然回溯法也是暴力，但至少能寫出來，不像for循環(huán)嵌套k層讓人絕望。
那么回溯法怎么暴力搜呢?
上面我們說了要解決 n為100，k為50的情況，暴力寫法需要嵌套50層for循環(huán)，那么回溯法就用遞歸來解決嵌套層數(shù)的問題。
遞歸來做層疊嵌套(可以理解是開k層for循環(huán))，每一次的遞歸中嵌套一個(gè)for循環(huán)，那么遞歸就可以用于解決多層嵌套循環(huán)的問題了。
此時(shí)遞歸的層數(shù)大家應(yīng)該知道了，例如：n為100，k為50的情況下，就是遞歸50層。
一些同學(xué)本來對(duì)遞歸就懵，回溯法中遞歸還要嵌套for循環(huán)，可能就直接暈倒了!
如果腦洞模擬回溯搜索的過程，絕對(duì)可以讓人窒息，所以需要抽象圖形結(jié)構(gòu)來進(jìn)一步理解。
我們?cè)陉P(guān)于回溯算法，你該了解這些!中說道回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)(N叉樹)，用樹形結(jié)構(gòu)來理解回溯就容易多了。
那么我把組合問題抽象為如下樹形結(jié)構(gòu)：
77.組合
可以看出這個(gè)棵樹，一開始集合是 1，2，3，4， 從左向右取數(shù)，取過的數(shù)，不在重復(fù)取。
第一次取1，集合變?yōu)?，3，4 ，因?yàn)閗為2，我們只需要再取一個(gè)數(shù)就可以了，分別取2，3，4，得到集合[1,2] [1,3] [1,4]，以此類推。
每次從集合中選取元素，可選擇的范圍隨著選擇的進(jìn)行而收縮，調(diào)整可選擇的范圍。
圖中可以發(fā)現(xiàn)n相當(dāng)于樹的寬度，k相當(dāng)于樹的深度。
那么如何在這個(gè)樹上遍歷，然后收集到我們要的結(jié)果集呢?
圖中每次搜索到了葉子節(jié)點(diǎn)，我們就找到了一個(gè)結(jié)果。
相當(dāng)于只需要把達(dá)到葉子節(jié)點(diǎn)的結(jié)果收集起來，就可以求得 n個(gè)數(shù)中k個(gè)數(shù)的組合集合。
在關(guān)于回溯算法，你該了解這些!中我們提到了回溯法三部曲，那么我們按照回溯法三部曲開始正式講解代碼了。
回溯法三部曲
遞歸函數(shù)的返回值以及參數(shù)
在這里要定義兩個(gè)全局變量，一個(gè)用來存放符合條件單一結(jié)果，一個(gè)用來存放符合條件結(jié)果的集合。
代碼如下：
- vector<vector<int>> result; // 存放符合條件結(jié)果的集合
- vector<int> path; // 用來存放符合條件結(jié)果
其實(shí)不定義這兩個(gè)全局遍歷也是可以的，把這兩個(gè)變量放進(jìn)遞歸函數(shù)的參數(shù)里，但函數(shù)里參數(shù)太多影響可讀性，所以我定義全局變量了。
函數(shù)里一定有兩個(gè)參數(shù)，既然是集合n里面取k的數(shù)，那么n和k是兩個(gè)int型的參數(shù)。
然后還需要一個(gè)參數(shù)，為int型變量startIndex，這個(gè)參數(shù)用來記錄本層遞歸的中，集合從哪里開始遍歷(集合就是[1,...,n] )。
為什么要有這個(gè)startIndex呢?
每次從集合中選取元素，可選擇的范圍隨著選擇的進(jìn)行而收縮，調(diào)整可選擇的范圍，就是要靠startIndex。
從下圖中紅線部分可以看出，在集合[1,2,3,4]取1之后，下一層遞歸，就要在[2,3,4]中取數(shù)了，那么下一層遞歸如何知道從[2,3,4]中取數(shù)呢，靠的就是startIndex。
組合2
所以需要startIndex來記錄下一層遞歸，搜索的起始位置。
那么整體代碼如下：
- vector<vector<int>> result; // 存放符合條件結(jié)果的集合
- vector<int> path; // 用來存放符合條件單一結(jié)果
- void backtracking(int n, int k, int startIndex)
回溯函數(shù)終止條件
什么時(shí)候到達(dá)所謂的葉子節(jié)點(diǎn)了呢?
path這個(gè)數(shù)組的大小如果達(dá)到k，說明我們找到了一個(gè)子集大小為k的組合了，在圖中path存的就是根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。
如圖紅色部分：
組合3
此時(shí)用result二維數(shù)組，把path保存起來，并終止本層遞歸。
所以終止條件代碼如下：
- if (path.size() == k) {
- result.push_back(path);
- return;
- }
- 單層搜索的過程
回溯法的搜索過程就是一個(gè)樹型結(jié)構(gòu)的遍歷過程，在如下圖中，可以看出for循環(huán)用來橫向遍歷，遞歸的過程是縱向遍歷。
組合1
如此我們才遍歷完圖中的這棵樹。
for循環(huán)每次從startIndex開始遍歷，然后用path保存取到的節(jié)點(diǎn)i。
代碼如下：
- for (int i = startIndex; i <= n; i++) { // 控制樹的橫向遍歷
- path.push_back(i); // 處理節(jié)點(diǎn)
- backtracking(n, k, i + 1); // 遞歸：控制樹的縱向遍歷，注意下一層搜索要從i+1開始
- path.pop_back(); // 回溯，撤銷處理的節(jié)點(diǎn)
- }
可以看出backtracking(遞歸函數(shù))通過不斷調(diào)用自己一直往深處遍歷，總會(huì)遇到葉子節(jié)點(diǎn)，遇到了葉子節(jié)點(diǎn)就要返回。
backtracking的下面部分就是回溯的操作了，撤銷本次處理的結(jié)果。
關(guān)鍵地方都講完了，組合問題C++完整代碼如下：
- class Solution {
- private:
- vector<vector<int>> result; // 存放符合條件結(jié)果的集合
- vector<int> path; // 用來存放符合條件結(jié)果
- void backtracking(int n, int k, int startIndex) {
- if (path.size() == k) {
- result.push_back(path);
- return;
- }
- for (int i = startIndex; i <= n; i++) {
- path.push_back(i); // 處理節(jié)點(diǎn)
- backtracking(n, k, i + 1); // 遞歸
- path.pop_back(); // 回溯，撤銷處理的節(jié)點(diǎn)
- }
- }
- public:
- vector<vector<int>> combine(int n, int k) {
- result.clear(); // 可以不寫
- path.clear(); // 可以不寫
- backtracking(n, k, 1);
- return result;
- }
- };
還記得我們?cè)陉P(guān)于回溯算法，你該了解這些!中給出的回溯法模板么?
如下：
- void backtracking(參數(shù)) {
- if (終止條件) {
- 存放結(jié)果;
- return;
- }
- for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) {
- 處理節(jié)點(diǎn);
- backtracking(路徑，選擇列表); // 遞歸
- 回溯，撤銷處理結(jié)果
- }
- }
對(duì)比一下本題的代碼，是不是發(fā)現(xiàn)有點(diǎn)像! 所以有了這個(gè)模板，就有解題的大體方向，不至于毫無頭緒。
總結(jié)
組合問題是回溯法解決的經(jīng)典問題，我們開始的時(shí)候給大家列舉一個(gè)很形象的例子，就是n為100，k為50的話，直接想法就需要50層for循環(huán)。
從而引出了回溯法就是解決這種k層for循環(huán)嵌套的問題。
然后進(jìn)一步把回溯法的搜索過程抽象為樹形結(jié)構(gòu)，可以直觀的看出搜索的過程。
接著用回溯法三部曲，逐步分析了函數(shù)參數(shù)、終止條件和單層搜索的過程。
剪枝優(yōu)化
我們說過，回溯法雖然是暴力搜索，但也有時(shí)候可以有點(diǎn)剪枝優(yōu)化一下的。
在遍歷的過程中有如下代碼：
- for (int i = startIndex; i <= n; i++) {
- path.push_back(i);
- backtracking(n, k, i + 1);
- path.pop_back();
- }
這個(gè)遍歷的范圍是可以剪枝優(yōu)化的，怎么優(yōu)化呢?
來舉一個(gè)例子，n = 4，k = 4的話，那么第一層for循環(huán)的時(shí)候，從元素2開始的遍歷都沒有意義了。在第二層for循環(huán)，從元素3開始的遍歷都沒有意義了。
這么說有點(diǎn)抽象，如圖所示：
組合4
圖中每一個(gè)節(jié)點(diǎn)(圖中為矩形)，就代表本層的一個(gè)for循環(huán)，那么每一層的for循環(huán)從第二個(gè)數(shù)開始遍歷的話，都沒有意義，都是無效遍歷。
所以，可以剪枝的地方就在遞歸中每一層的for循環(huán)所選擇的起始位置。
如果for循環(huán)選擇的起始位置之后的元素個(gè)數(shù) 已經(jīng)不足 我們需要的元素個(gè)數(shù)了，那么就沒有必要搜索了。
注意代碼中i，就是for循環(huán)里選擇的起始位置。
- for (int i = startIndex; i <= n; i++) {
接下來看一下優(yōu)化過程如下：
已經(jīng)選擇的元素個(gè)數(shù)：path.size();
還需要的元素個(gè)數(shù)為: k - path.size();
在集合n中至多要從該起始位置 : n - (k - path.size()) + 1，開始遍歷
為什么有個(gè)+1呢，因?yàn)榘ㄆ鹗嘉恢?，我們要是一個(gè)左閉的集合。
舉個(gè)例子，n = 4，k = 3， 目前已經(jīng)選取的元素為0(path.size為0)，n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
從2開始搜索都是合理的，可以是組合[2, 3, 4]。
這里大家想不懂的話，建議也舉一個(gè)例子，就知道是不是要+1了。
所以優(yōu)化之后的for循環(huán)是：
- for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i為本次搜索的起始位置
優(yōu)化后整體代碼如下：
- class Solution {
- private:
- vector<vector<int>> result;
- vector<int> path;
- void backtracking(int n, int k, int startIndex) {
- if (path.size() == k) {
- result.push_back(path);
- return;
- }
- for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 優(yōu)化的地方
- path.push_back(i); // 處理節(jié)點(diǎn)
- backtracking(n, k, i + 1);
- path.pop_back(); // 回溯，撤銷處理的節(jié)點(diǎn)
- }
- }
- public:
- vector<vector<int>> combine(int n, int k) {
- backtracking(n, k, 1);
- return result;
- }
- };
剪枝總結(jié)
本篇我們準(zhǔn)對(duì)求組合問題的回溯法代碼做了剪枝優(yōu)化，這個(gè)優(yōu)化如果不畫圖的話，其實(shí)不好理解，也不好講清楚。
所以我依然是把整個(gè)回溯過程抽象為一顆樹形結(jié)構(gòu)，然后可以直觀的看出，剪枝究竟是剪的哪里。
其他語言版本
Java
- class Solution {
- List<List<Integer>> result = new ArrayList<>();
- LinkedList<Integer> path = new LinkedList<>();
- public List<List<Integer>> combine(int n, int k) {
- combineHelper(n, k, 1);
- return result;
- }
- /**
- * 每次從集合中選取元素，可選擇的范圍隨著選擇的進(jìn)行而收縮，調(diào)整可選擇的范圍，就是要靠startIndex
- * @param startIndex 用來記錄本層遞歸的中，集合從哪里開始遍歷（集合就是[1,...,n] ）。
- */
- private void combineHelper(int n, int k, int startIndex){
- //終止條件
- if (path.size() == k){
- result.add(new ArrayList<>(path));
- return;
- }
- for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
- path.add(i);
- combineHelper(n, k, i + 1);
- path.removeLast();
- }
- }
- }
Python
- class Solution:
- def combine(self, n: int, k: int) -> List[List[int]]:
- res=[] #存放符合條件結(jié)果的集合
- path=[] #用來存放符合條件結(jié)果
- def backtrack(n,k,startIndex):
- if len(path) == k:
- res.append(path[:])
- return
- for i in range(startIndex,n+1):
- path.append(i) #處理節(jié)點(diǎn)
- backtrack(n,k,i+1) #遞歸
- path.pop() #回溯，撤銷處理的節(jié)點(diǎn)
- backtrack(n,k,1)
- return res
Go
- var res [][]int
- func combine(n int, k int) [][]int {
- res=[][]int{}
- if n <= 0 || k <= 0 || k > n {
- return res
- }
- backtrack(n, k, 1, []int{})
- return res
- }
- func backtrack(n,k,start int,track []int){
- if len(track)==k{
- temp:=make([]int,k)
- copy(temp,track)
- res=append(res,temp)
- }
- if len(track)+n-start+1 < k {
- return
- }
- for i:=start;i<=n;i++{
- track=append(track,i)
- backtrack(n,k,i+1,track)
- track=track[:len(track)-1]
- }
- }
