組合

力扣題目鏈接：https://leetcode-cn.com/problems/combinations/

給定兩個整數 n 和 k，返回 1 ... n 中所有可能的 k 個數的組合。

示例: 輸入: n = 4, k = 2 輸出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

本題這是回溯法的經典題目。

直接的解法當然是使用for循環，例如示例中k為2，很容易想到 用兩個for循環，這樣就可以輸出 和示例中一樣的結果。

代碼如下：

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循環，代碼如下：

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循環，是不是開始窒息。

此時就會發現雖然想暴力搜索，但是用for循環嵌套連暴力都寫不出來!

咋整?

回溯搜索法來了，雖然回溯法也是暴力，但至少能寫出來，不像for循環嵌套k層讓人絕望。

那么回溯法怎么暴力搜呢?

上面我們說了要解決 n為100，k為50的情況，暴力寫法需要嵌套50層for循環，那么回溯法就用遞歸來解決嵌套層數的問題。

遞歸來做層疊嵌套(可以理解是開k層for循環)，每一次的遞歸中嵌套一個for循環，那么遞歸就可以用于解決多層嵌套循環的問題了。

此時遞歸的層數大家應該知道了，例如：n為100，k為50的情況下，就是遞歸50層。

一些同學本來對遞歸就懵，回溯法中遞歸還要嵌套for循環，可能就直接暈倒了!

如果腦洞模擬回溯搜索的過程，絕對可以讓人窒息，所以需要抽象圖形結構來進一步理解。

我們在關于回溯算法，你該了解這些!中說道回溯法解決的問題都可以抽象為樹形結構(N叉樹)，用樹形結構來理解回溯就容易多了。

那么我把組合問題抽象為如下樹形結構：

77.組合

可以看出這個棵樹，一開始集合是 1，2，3，4， 從左向右取數，取過的數，不在重復取。

第一次取1，集合變為2，3，4 ，因為k為2，我們只需要再取一個數就可以了，分別取2，3，4，得到集合[1,2] [1,3] [1,4]，以此類推。

每次從集合中選取元素，可選擇的范圍隨著選擇的進行而收縮，調整可選擇的范圍。

圖中可以發現n相當于樹的寬度，k相當于樹的深度。

那么如何在這個樹上遍歷，然后收集到我們要的結果集呢?

圖中每次搜索到了葉子節點，我們就找到了一個結果。

相當于只需要把達到葉子節點的結果收集起來，就可以求得 n個數中k個數的組合集合。

在關于回溯算法，你該了解這些!中我們提到了回溯法三部曲，那么我們按照回溯法三部曲開始正式講解代碼了。

回溯法三部曲

遞歸函數的返回值以及參數

在這里要定義兩個全局變量，一個用來存放符合條件單一結果，一個用來存放符合條件結果的集合。

代碼如下：

vector<vector<int>> result; // 存放符合條件結果的集合 
vector<int> path; // 用來存放符合條件結果 

其實不定義這兩個全局遍歷也是可以的，把這兩個變量放進遞歸函數的參數里，但函數里參數太多影響可讀性，所以我定義全局變量了。

函數里一定有兩個參數，既然是集合n里面取k的數，那么n和k是兩個int型的參數。

然后還需要一個參數，為int型變量startIndex，這個參數用來記錄本層遞歸的中，集合從哪里開始遍歷(集合就是[1,...,n] )。

為什么要有這個startIndex呢?

每次從集合中選取元素，可選擇的范圍隨著選擇的進行而收縮，調整可選擇的范圍，就是要靠startIndex。

從下圖中紅線部分可以看出，在集合[1,2,3,4]取1之后，下一層遞歸，就要在[2,3,4]中取數了，那么下一層遞歸如何知道從[2,3,4]中取數呢，靠的就是startIndex。

組合2

所以需要startIndex來記錄下一層遞歸，搜索的起始位置。

那么整體代碼如下：

vector<vector<int>> result; // 存放符合條件結果的集合 
vector<int> path; // 用來存放符合條件單一結果 
void backtracking(int n, int k, int startIndex) 

回溯函數終止條件

什么時候到達所謂的葉子節點了呢?

path這個數組的大小如果達到k，說明我們找到了一個子集大小為k的組合了，在圖中path存的就是根節點到葉子節點的路徑。

如圖紅色部分：

組合3

此時用result二維數組，把path保存起來，并終止本層遞歸。

所以終止條件代碼如下：

if (path.size() == k) { 
    result.push_back(path); 
    return; 
} 

• 單層搜索的過程

回溯法的搜索過程就是一個樹型結構的遍歷過程，在如下圖中，可以看出for循環用來橫向遍歷，遞歸的過程是縱向遍歷。

組合1

如此我們才遍歷完圖中的這棵樹。

for循環每次從startIndex開始遍歷，然后用path保存取到的節點i。

代碼如下：

for (int i = startIndex; i <= n; i++) { // 控制樹的橫向遍歷 
    path.push_back(i); // 處理節點 
    backtracking(n, k, i + 1); // 遞歸：控制樹的縱向遍歷，注意下一層搜索要從i+1開始 
    path.pop_back(); // 回溯，撤銷處理的節點 
} 

可以看出backtracking(遞歸函數)通過不斷調用自己一直往深處遍歷，總會遇到葉子節點，遇到了葉子節點就要返回。

backtracking的下面部分就是回溯的操作了，撤銷本次處理的結果。

關鍵地方都講完了，組合問題C++完整代碼如下：

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; i++) { 
            path.push_back(i); // 處理節點 
            backtracking(n, k, i + 1); // 遞歸 
            path.pop_back(); // 回溯，撤銷處理的節點 
        } 
    } 
public: 
    vector<vector<int>> combine(int n, int k) { 
        result.clear(); // 可以不寫 
        path.clear();   // 可以不寫 
        backtracking(n, k, 1); 
        return result; 
    } 
}; 

還記得我們在關于回溯算法，你該了解這些!中給出的回溯法模板么?

如下：

void backtracking(參數) { 
    if (終止條件) { 
        存放結果; 
        return; 
    } 
 
    for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大?。? { 
        處理節點; 
        backtracking(路徑，選擇列表); // 遞歸 
        回溯，撤銷處理結果 
    } 
} 

對比一下本題的代碼，是不是發現有點像! 所以有了這個模板，就有解題的大體方向，不至于毫無頭緒。

總結

組合問題是回溯法解決的經典問題，我們開始的時候給大家列舉一個很形象的例子，就是n為100，k為50的話，直接想法就需要50層for循環。

從而引出了回溯法就是解決這種k層for循環嵌套的問題。

然后進一步把回溯法的搜索過程抽象為樹形結構，可以直觀的看出搜索的過程。

接著用回溯法三部曲，逐步分析了函數參數、終止條件和單層搜索的過程。

剪枝優化

我們說過，回溯法雖然是暴力搜索，但也有時候可以有點剪枝優化一下的。

在遍歷的過程中有如下代碼：

for (int i = startIndex; i <= n; i++) { 
    path.push_back(i); 
    backtracking(n, k, i + 1); 
    path.pop_back(); 
} 

這個遍歷的范圍是可以剪枝優化的，怎么優化呢?

來舉一個例子，n = 4，k = 4的話，那么第一層for循環的時候，從元素2開始的遍歷都沒有意義了。在第二層for循環，從元素3開始的遍歷都沒有意義了。

這么說有點抽象，如圖所示：

組合4

圖中每一個節點(圖中為矩形)，就代表本層的一個for循環，那么每一層的for循環從第二個數開始遍歷的話，都沒有意義，都是無效遍歷。

所以，可以剪枝的地方就在遞歸中每一層的for循環所選擇的起始位置。

如果for循環選擇的起始位置之后的元素個數 已經不足 我們需要的元素個數了，那么就沒有必要搜索了。

注意代碼中i，就是for循環里選擇的起始位置。

for (int i = startIndex; i <= n; i++) { 

接下來看一下優化過程如下：

已經選擇的元素個數：path.size();

還需要的元素個數為: k - path.size();

在集合n中至多要從該起始位置 : n - (k - path.size()) + 1，開始遍歷

為什么有個+1呢，因為包括起始位置，我們要是一個左閉的集合。

舉個例子，n = 4，k = 3， 目前已經選取的元素為0(path.size為0)，n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

從2開始搜索都是合理的，可以是組合[2, 3, 4]。

這里大家想不懂的話，建議也舉一個例子，就知道是不是要+1了。

所以優化之后的for循環是：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i為本次搜索的起始位置 

優化后整體代碼如下：

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++) { // 優化的地方 
            path.push_back(i); // 處理節點 
            backtracking(n, k, i + 1); 
            path.pop_back(); // 回溯，撤銷處理的節點 
        } 
    } 
public: 
 
    vector<vector<int>> combine(int n, int k) { 
        backtracking(n, k, 1); 
        return result; 
    } 
}; 

剪枝總結

本篇我們準對求組合問題的回溯法代碼做了剪枝優化，這個優化如果不畫圖的話，其實不好理解，也不好講清楚。

所以我依然是把整個回溯過程抽象為一顆樹形結構，然后可以直觀的看出，剪枝究竟是剪的哪里。

其他語言版本

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; 
    } 
 
    /** 
     * 每次從集合中選取元素，可選擇的范圍隨著選擇的進行而收縮，調整可選擇的范圍，就是要靠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=[]  #存放符合條件結果的集合 
        path=[]  #用來存放符合條件結果 
        def backtrack(n,k,startIndex): 
            if len(path) == k: 
                res.append(path[:]) 
                return 
            for i in range(startIndex,n+1): 
                path.append(i)  #處理節點 
                backtrack(n,k,i+1)  #遞歸 
                path.pop()  #回溯，撤銷處理的節點 
        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] 
    } 
}