一句话答案

回溯 = DFS + 剪枝：for 选择列表 { 剪枝→做选择→递归→撤销选择 }，适用于排列/组合/子集/棋盘问题。

核心要点

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

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

追问与易错

追问方向：

• 回溯和 DFS 的区别？
• 怎么剪枝提升效率？
• 回溯的时间复杂度怎么分析？

易错点：

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

💡 记忆锚点

回溯像走迷宫：每个岔路口做一个选择往前走（递归），走不通就退回来擦掉脚印（撤销选择）换条路。模板口诀"选剪做递撤"：遍历选择列表→剪枝（此路不通直接跳过）→做选择→递归下一层→撤销选择。排列用visited标记，组合用start索引避免重复。没有剪枝就是暴力，剪枝才是灵魂。