今天是LeetCode第46篇文章，我們一起來LeetCode中的77題，Combinations（組合）。

這個題目可以說是很精闢了，僅僅用一個單詞的標題就說清楚了大半題意了。這題官方難度是Medium，它在LeetCode當中評價很高，1364人點贊，只有66個反對。通過率53.6%。

題意

題目的題意很簡單，給定兩個整數n和k。n表示從1到n的n個自然數，要求隨機從這n個數中抽取k個的所有組合。

樣例

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

全排列的問題我們已經很熟悉了，那麼獲取組合的問題怎麼做呢？

遞歸

這是一個全組合問題，實際上我們之前做過全排列問題。我們來分析一下排列和組合的區別，可能很多人知道這兩者的區別，但是對於區別本身的理解和認識不是非常深刻。

排列和組合有一個巨大的區別在於，排列會考慮物體擺放的順序。也就是說同樣的元素構成，只要這些元素一些交換順序，那麼就會被視為是不同的排列。然而對於組合來說，是不會考慮物體的擺放順序的。只要是這些元素構成，無論它們怎麼調換擺放順序，都是同一種組合。

我們獲取全排列的時候用的是回溯法，我們當然也可以用回溯法來獲取組合。但問題是，我們怎麼保證獲取到的組合都是元素的組成不同，而不是元素之間的順序不同呢？

為了保證這一點，需要用到一個慣用的小套路，就是通過下標遞增來控制拿取元素的順序。如果我們限定了拿取元素的下標是遞增的，那麼就可以保證每一次拿取到的組合都是獨一無二的。所以我們就把這一點加在回溯法上即可，只要理解了，並不難實現。

在代碼的實現當中，我們用上了閉包，省略了幾個參數的傳遞，整體上來說編碼的難度降低了一些。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(start, cur):
            # 如果當前已經拿到了K個數的組合，直接加入答案
            # 注意要做深拷貝，否則在之後的回溯過程當中變動也會影響結果
            if len(cur) == k:
                ret.append(cur[:])
                return
            
            # 從start+1的位置開始遍歷
            for i in range(start+1, n):
                cur.append(i+1)
                dfs(i, cur)
                # 回溯
                cur.pop()
                
        ret = []
        dfs(-1, [])
        return ret

迭代

這題並不是只有一種做法，我們也可以不用遞歸實現算法。不用遞歸意味着沒有系統幫助我們建棧存儲中間信息了，需要我們自己把迭代過程當中所有變量的關係整理清楚。

我們假設n=8，k=3，那麼在所有合法的組合當中，最小的組合一定是[1,2,3]，最大的組合一定是[6,7,8]。如果我們保證組合當中的元素是有序排列的，那麼組合之間的大小關係也是可以確定的。進而我們可以思考設計一種方案，使得我們可以從最小的組合[1,2,3]一直迭代到[6,7,8]，並且我們還要保證在迭代的過程當中，組合當中元素的順序不會被打亂。

我們可以想象成這n個數在一根“直尺”上排成了一行，我們有k個滑動框在上面移動。這k個滑動框取值的結果就是n個元素中選取k個的組合，並且由於滑動框之間是不能交錯的，所以保證了這k個值是有序的。我們要做的就是設計一種移動滑動框的算法，使得能夠找到所有的組合情況。

我們可以想象一下，一開始的時候滑動框都聚集在最左邊，我們要移動只能移動最右側的滑動框。我們把滑動框從k移動到了k+1，那麼這個時候它的右側有k-1個滑動框，一共有k個位置。

那麼這個問題其實轉化成了k個元素當中取k-1個組合的子問題。我們把1-k的這個部分看成是新的“直尺”，我們要在其中移動k-1個滑動框獲取所有的組合。首先，我們需要把這k-1個滑動框全部移動到左側，然後再移動其中最右側的滑動框。然後循環往複，直到所有的滑動框都往右移動了一格為止，這其實是一個遞歸的過程。

我們不去深究這個遞歸的整個過程，我們只需要理解清楚其中的幾個關鍵點就可以了。首先，對於每一次遞歸來說，我們只會移動這個遞歸範圍內最右側的滑動框，其次我們清楚每一次遞歸過程中的起始狀態。開始狀態就是所有的滑動框全部集中在“直尺”的最左側，結束狀態就是全部集中在最右側。

我們把上面的邏輯整理一下，假設我們經過一系列操作之後，m個滑動框全部移動到了長度為n的直尺的最右側。這就相當於的組合都已經獲取完了。如果n+1的位置還有滑動框，並且它的右側還可以移動，那麼我們需要將它往右移動一個，到n+2的位置。這個時候剩下的局面就是，為了獲取這些組合，我們需要把這m個滑動框全部再移動到直尺的最左側，重新開始移動。

我們在實現的時候當然沒有滑動框，我們可以用一個數組記錄滑動框當中的元素。

我先用遞歸寫一下這段邏輯：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def comb(window, m, ret):
            ret.append(window[:-1])

            # 如果第m位的滑動框不超過直尺的範圍並且m右側的滑動框
            while window[m] < min(n - k + m + 1, window[m+1] - 1):
                # 向右滑動一位
                window[m] += 1
                # 如果m左側還有滑動框，遞歸
                if m > 0:
                    # 把左側的滑動框全部移動到最左側
                    window[:m] = range(1, m+1)
                    comb(window, m-1, ret)
                else:
                    # 否則記錄答案
                    ret.append(window[:-1])

                
        ret = []
        window = list(range(1, k+1))
        # 額外多放一個滑動框作為標兵
        window.append(n+1)
        comb(window, k-1, ret)
        return ret

這種解法的速度比上面正規遞歸的速度快了許多，因為我們遞歸的過程當中做了諸多限制，剪掉了很多無關的情況，相當於做了極致的剪枝。

最關鍵的是上面的這段邏輯我們是可以用循環實現的，所以我們可以用循環來將遞歸的邏輯展開，就得到了下面這段代碼。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 構造滑動框
        window = list(range(1, k + 1)) + [n + 1]
        
        ret, j = [], 0

        while j < k:
            # 添加答案
            ret.append(window[:k])

            j = 0
            # 從最左側的滑動框開始判斷
            # 如果滑動框與它右側滑動框挨着，那麼就將它移動到最左側
            # 因為它右側的滑動框一定會向右移動
            while j < k and window[j + 1] == window[j] + 1:
                window[j] = j + 1
                j += 1
            # 連續挨着最右側的滑動框向右移動一格
            window[j] += 1
            
        return ret

這段代碼雖然非常精鍊，但是很難理解，尤其是你沒能理解上面遞歸實現的話，會更難理解。所以我建議，先把遞歸實現的滑動框的方法理解了，再來理解不含遞歸的這段，會容易一些。

總結

我們通過回溯法求解組合的方法應該是最簡單也是最基礎的，難度也不大。相比之下後面一種方法則要困難許多，我們直接去啃，往往不得要領。既會疑惑為什麼這樣可以保證能獲得所有的組合，又會不明白其中具體的實現邏輯。所以如果想要弄明白第二種方法，一定要從滑動框這個模型出發。

從代碼實現的角度來說，滑動框方法的遞歸解法比非遞歸的解法還要困難。因為遞歸條件以及邏輯都比較複雜，還涉及到存儲答案的問題。但是從理解上來說，遞歸的解法更加容易理解一些，非遞歸的算法往往會疑惑於j這個指針的取值。所以如果想要理解算法的話，可以從遞歸的代碼入手，想要實現代碼的話，可以從非遞歸的方法入手。

這道題目非常有意思，值得大家細細思考。

如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也方便獲取更多文章。

本文使用 mdnice 排版