本文始發於個人公眾號：TechFlow，原創不易，求個關注
今天是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 排版
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面
※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!
※想知道最厲害的網頁設計公司"嚨底家"!
※別再煩惱如何寫文案,掌握八大原則!
※產品缺大量曝光嗎?你需要的是一流包裝設計!
