回溯法

回溯法也可以叫做回溯搜索法，它是一種搜索的方式。

回溯是遞歸的副產(chǎn)品，只要有遞歸就會有回溯?；厮莺瘮?shù)也就是遞歸函數(shù)，指的都是一個函數(shù)。

1. 回溯法的效率

純暴力搜索，本質(zhì)是窮舉所有可能，然后選出想要的結(jié)果

2. 回溯法解決的問題
   組合問題（組合無序）
   切割問題
   子集問題
   排列問題（排列有序）
   棋盤問題

3. 理解回溯法

回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)
回溯法解決的都是在集合中遞歸查找子集，集合的大小就構(gòu)成了樹的寬度，遞歸的深度，都構(gòu)成的樹的深度
遞歸就要有終止條件，所以必然是一棵高度有限的樹（N叉樹）。

4. 回溯法模板

def backtracking(para,...):
    if 終止條件:
        收集結(jié)果
        return
    for i in 幾何元素集:
        處理節(jié)點(diǎn)
        遞歸函數(shù)
        回溯，撤銷處理結(jié)果
    return

77. 組合問題

解題步驟

1. 轉(zhuǎn)換樹形結(jié)構(gòu)

   
   

2. 遞歸函數(shù)參數(shù)返回值
   n（題目提供）：數(shù)字個數(shù)
   k（題目提供）：組合大小
   start_index ：每次遞歸搜索的起始位置
   path（一維數(shù)組） ：收集路徑
   result（二維數(shù)組） ：存放返回結(jié)果

3. 確定終止條件

if len(path) == k:
    result.append(path[:])
    return

4. 單層遞歸邏輯

for i in range(start_index, n + 1):
    path.append(i)
    backtracking(n, k, i + 1)
    path.pop()

最終代碼

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        
        path = []
        result = []
        def backtracking(n, k, start_index):
            if len(path) == k:
                result.append(path[:]) # 這里為啥是path[:]
                return
            #for i in range(start_index, n + 1):
            # 優(yōu)化剪枝
            for i in range(start_index, n - (k - len(path)) + 2):
                path.append(i)
                backtracking(n, k, i + 1)
                path.pop()
        backtracking(n, k, 1) # start_index表是從數(shù)字1開始搜索
        return result