回溯算法与 DFS 的系统总结

组合、排列、路径搜索

🧠 一、回溯和 DFS 的关系

回溯是 DFS 的一个“特化”版本，专门用于构造类问题的解空间搜索。

📦 二、回溯算法的模板

回溯模版能够使用的核心就是这五点，其中2我认为是最重要的，2觉得了递归函数的入参。

1. path 是什么？（当前构造了什么？）
2. choices 是什么？（接下来还能选什么？）
3. 什么时候结束？（递归终点 + 加入结果）
4. 剪枝能不能提前排除非法？
5. 状态如何恢复？（pop）

 1def backtrack(path, choices):
 2    if 满足结束条件:
 3        res.append(path[:])  # 深拷贝保存路径
 4        return
 5    for choice in choices:
 6        if 剪枝条件:
 7            continue
 8        path.append(choice) # 做选择
 9        backtrack(path, updated_choices)
10        path.pop() # 撤销选择

变量说明：

• path: 当前构造的解（例如排列、子集等）
• choices: 当前可选的元素（如剩余数字、起始下标等）
• res: 最终结果集合

几种常见情况的补充说明:

1. python做回溯的时候，path变量可以在闭包外部定义，不用每次在递归中传递。因为有撤销选择时path的pop()操作和进入递归时path[:]深拷贝来保证没问题。
2. 一般数组可以通过起点index来控制choices，所以经常的变体是backtrack(start_idx), backtrack(cur_idx + 1)就一个变量参与递归就够了。
3. 一般剪枝条件可能需要累积计算判断，这样可以在递归时传递一个值，递归前计算，递归后反向计算。一般就是求和之类的。

🌟 三、题型分类与识别套路

✂️ 四、常见剪枝技巧

🌲 五、回溯搜索树示意（组合总和）

以 combinationSum([2,3,6,7], target=7) 为例：

1                    []
2         /      /       \         \
3      [2]     [3]      [6]       [7]
4      /        |
5   [2,2]     [3,3]
6    ...

每层递归相当于“树的一个深度”，每个选择分支是一条“路径”。

📌 六、实战建议

• 回溯问题 = 在解空间树上做 DFS，到叶子节点检查是否合法

• 通常可归纳为三步：

  1. 选择：从当前可选列表中挑一个
  2. 递归：继续搜索
  3. 撤销：回退这一步，继续试下一个

• 关键是掌握两个概念：

  • “路径”（你构造的部分答案）
  • “选择列表”（你当前还能选谁）

🔁 七、建议刷题顺序（从易到难）

1. 组合问题：77. 组合、216. 组合总和 III
2. 排列问题：46. 全排列、47. 全排列 II
3. 子集问题：78. 子集、90. 子集 II
4. 分割问题：131. 分割回文串、93. 复原 IP
5. 板子题练熟后挑战：51. N皇后、37. 数独、79. 单词搜索

• ⇦
  双指针
• ⇨
  动态规划