回溯算法模板#

模板： for(选择) { 剪枝 → 做选择 → 递归 → 撤销 }

经典题： 全排列(visited数组) / 组合总和(start索引) / N皇后(冲突检测) / 子集(选或不选)

回溯本质上是带剪枝的DFS，核心模板五个字”选剪做递撤”。具体来说，遍历当前层的选择列表，先判断能不能剪枝，能就跳过；不能就做选择（比如把元素加入路径），然后递归进入下一层，递归返回后必须撤销选择恢复现场。经典题型包括全排列（用visited数组标记已用元素）、组合总和（用start索引避免重复选取）、N皇后（通过列/对角线冲突检测剪枝）和子集问题（每个元素选或不选两种分支）。回溯和纯暴力的区别就在剪枝——没有剪枝确实是暴力枚举，加了剪枝可以大幅缩减搜索空间。时间复杂度分析看递归树的节点数，通常是O(n!)或O(2^n)级别，但剪枝后实际远小于上界。

追问方向：

• “回溯和 DFS 的区别？”→ DFS 是遍历策略，回溯是在 DFS 基础上加「撤销选择」来穷举所有方案；回溯强调状态回退，DFS 侧重图/树的深度遍历
• “怎么剪枝提升效率？”→ 排序后跳过重复元素、提前判断剩余元素不可能满足条件就 return、用 visited 数组避免重复访问、利用约束条件缩小搜索范围
• “回溯的时间复杂度怎么分析？”→ 看递归树的节点数：子集问题 O(2^n)、排列问题 O(n!)、组合问题 O(C(n,k))；剪枝能减少实际节点数但不改变最坏复杂度量级

易错点：

• ❌ 回溯就是暴力搜索——加了剪枝可以大幅减少搜索空间
• ❌ 回溯不需要恢复状态——必须撤销选择