leetcode(力扣) 77. 組合（回溯 & 剪枝-----清晰圖解+回溯套路模闆）

文章目錄

• 題目描述
• 思路分析
• 完整代碼
• 優化(剪枝)；
• 完整代碼

題目描述

給定兩個整數 n 和 k，傳回範圍 [1, n] 中所有可能的 k 個數的組合。

你可以按 任何順序 傳回答案。

示例 1：

輸入：n = 4, k = 2

輸出：

[

[2,4],

[3,4],

[2,3],

[1,2],

[1,3],

[1,4],

]

示例 2：

輸入：n = 1, k = 1

輸出：[[1]]

思路分析

一道回溯經典應用題。

題目要求的是組合 不是排列，也就是 [1,2] [2,1] 是一個答案，别弄錯了。

回溯 、遞歸模闆

• 确定遞歸參數
• 确定終止條件
• 确定單次循環體

這種回溯的題，都可以畫成樹形結構，不熟的時候，先畫圖看看邏輯，

假設n=4 k=2，也就是四個數選兩兩組合，看下圖：

1.确定 遞歸/回溯 參數：

首先需要題目給出的n和k沒跑了，另外還有一個，可以在圖中看到，當選擇1之後，隻能從2，3，4裡再選，選擇2之後，隻能從剩下的3，4裡選，也就是，選擇i之後，隻能從i+1裡去選，是以要有一個記錄下标的值startindex。

2.确定終止條件：

這個比較好想，當用來記錄的數組裡已經有k個值了，那麼就終止。

在終止之前，要将收集到的數加入到答案集。

if len(temp) == k:
     res.append(temp[:])
     return
           

3.确定循環體：

循環體裡也就是從一層到下面一層 and 下面一層回溯到上面一層 的過程中需要操作的東西。

首先需要将目前的 元素放到記錄的數組中，然後調用自己，最後回溯的時候記着彈出元素。

temp.append(i)
backtrack(n,k,i+1)
temp.pop()
           

細節：

1. 回溯的過程比較抽象，題也比較難想，可以畫出來樹圖，然後用套路化記憶，回調函數上面就是從本層到下一層需要操作的東西，回調函數下面就是從下一層傳回到上一層需要操作的東西，畢竟從終止條件return之後就要開始運作回調函數下面的内容了，也就是當記錄數組中達到k個值之後，顯然要pop彈出一個數，然後傳回到上一層樹中去。

比如：

temp.append(i)      # 這就是從本層到下一層需要做的事
backtrack(n,k,i+1)   # 這就是回調函數
temp.pop()    # 這就是從下一層到上一層需要做的事
           

1. 循環體中控制的是n，也就是樹的橫向，而不斷遞歸 ，回溯的過程中控制的是樹的縱向，也就是樹的深度。搞清楚這個小細節，則for裡的值就不會出錯了。
2. 要搞清楚for裡的i循環變量和startindex變量。for裡的startindex，可以這麼了解，每次橫向循環，外面的for裡的i控制從1到n,而假如選擇了1，後面還要選擇234，這個234是下一層的，也是橫向，在下一層中，第一個分支選擇了2，再下一層就是從3，4裡面選，是以startindex控制的是下一層從哪裡開始選擇，這個下一層，也是屬于橫向周遊的過程，可以看那個圖。

完整代碼

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]: 
            res = []
            temp = []
            def backtrack(n,k,startindex):
                # 終止條件
                if len(temp) == k:
                    res.append(temp[:]) 
                    #假設說如果你直接加入temp的話，那麼temp一定是你一開始要設定得全局變量得一個數組list對吧，然後你每次都往res中存入得temp其實就是一個指針，當你遞歸完以後，回溯，将path裡的最後一個資料删除了，那麼res中存入得元素指針，指向得那個數組同樣需要删除那個元素，最後就會導緻，你在res中開辟了多個空間，但是最後每個數組指代得是同一塊空間，并且最後該空間内得所有元素，最後都是空。
                    return
                # 循環體
                for i in range(startindex,n+1): # 記着+1，題目n從1開始的
                    temp.append(i)
                    backtrack(n,k,i+1)
                    temp.pop()
            backtrack(n,k,1)
            return res
           

優化(剪枝)；

回溯其實就是純暴力算法，隻是有時候不能無腦嵌套for，倒不是時間複雜度的問題，而是有時候根本沒法寫，比如這個題的for，有幾個k就有幾層嵌套for，但是k不确定，是以沒法寫。

當使用回溯的時候，往往搭配着剪枝，以降低時間複雜度。

假設n=4，k=4 也就是 一共四個數，取4個數，這裡盜用一下卡哥的圖，可以看到 除了最左邊的一條，其餘都不符合要求，都可以剪掉。

那麼如何在代碼中控制需要剪掉的分支呢？

假設目前n=4 ,k=3。看一下需要剪掉的部分，當記錄數組temp中為空，且目前i取3的時候，剩下可取元素為4，那麼取了3再進入一下分支取4，temp中也僅有兩個值。顯然這個i=3的分支是需要剪掉的，也就是 當你temp數組中個數+還需要的元素個數>剩下可選的元素個數時，剪！ 換句話說，你的 i 最多隻能周遊到2，周遊到2，temp裡是2，然後還能取3和4，此時正好為3個元素。

也就是說找一個公式來控制 i 最多可以周遊到的值，使得剩下未周遊的元素+temp裡現有的元素可以滿足k的要求

剩下未周遊的元素就是 元素總和n - 目前周遊到的下标i， -> n-i

即：(多項式優化)

• n-i+len(temp) >= k
• -i >= k-n-len(temp)
• i <= n+len(temp)-k

是以for裡的 i 條件是 i <= n-(k-len(temp), 也就是最多周遊到這，而之前是直接周遊到n+1。

實際上代碼裡是n-(k-len(temp))+1+1 ，為啥要+1兩次呢，随便帶個k和n就知道了，其實是題目n從1開始的原因。另一個+1就是無剪枝的情況下帶的。

完整代碼

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]: 
        # 帶剪枝
            res = []
            temp =[]
            def backtrack(n,k,startindex):
                # 終止條件
                if len(temp) == k:
                    res.append(temp[:])
                    return
                for i in range(startindex,n-(k-len(temp))+1+1):
                    temp.append(i)
                    backtrack(n,k,i+1)
                    temp.pop()
            backtrack(n,k,1)
            return res