回溯法

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

回溯是递归的副产品，只要有递归就会有回溯。回溯函数也就是递归函数，指的都是一个函数。

1. 回溯法的效率

纯暴力搜索，本质是穷举所有可能，然后选出想要的结果

2. 回溯法解决的问题
   组合问题（组合无序）
   切割问题
   子集问题
   排列问题（排列有序）
   棋盘问题

3. 理解回溯法

回溯法解决的问题都可以抽象为树形结构
回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

4. 回溯法模板

def backtracking(para,...):
    if 终止条件:
        收集结果
        return
    for i in 几何元素集:
        处理节点
        递归函数
        回溯，撤销处理结果
    return

77. 组合问题

解题步骤

1. 转换树形结构

   
   

2. 递归函数参数返回值
   n（题目提供）：数字个数
   k（题目提供）：组合大小
   start_index ：每次递归搜索的起始位置
   path（一维数组） ：收集路径
   result（二维数组） ：存放返回结果

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):
            # 优化剪枝
            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表是从数字1开始搜索
        return result