回溯法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。回溯函数也就是递归函数，指的都是一个函数。
- 回溯法的效率
纯暴力搜索，本质是穷举所有可能，然后选出想要的结果
回溯法解决的问题
组合问题（组合无序）
切割问题
子集问题
排列问题（排列有序）
棋盘问题理解回溯法
回溯法解决的问题都可以抽象为树形结构
回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
- 回溯法模板
def backtracking(para,...):
if 终止条件:
收集结果
return
for i in 几何元素集:
处理节点
递归函数
回溯，撤销处理结果
return
77. 组合问题
解题步骤
-
转换树形结构
递归函数参数返回值
n（题目提供）：数字个数
k（题目提供）：组合大小
start_index ：每次递归搜索的起始位置
path（一维数组） ：收集路径
result（二维数组） ：存放返回结果确定终止条件
if len(path) == k:
result.append(path[:])
return
- 单层递归逻辑
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
