回溯算法与经典题型
哪些公司问过
答案要点
- 回溯框架:做选择 → 递归 → 撤销选择;本质是穷举加剪枝
- 全排列:used 数组标记,或 swap 交换后递归再交换回来
- 组合与子集:用起始下标 start 避免重复;子集每个节点都加入结果
- 有重复元素:先排序;组合与子集用 i > start 且 nums[i] == nums[i-1] 跳过,全排列用 !used[i-1] 去重
- 复杂度指数级,通过剪枝(如和超过目标提前返回)减少搜索
易错点
- 忘了撤销选择,状态被污染
- 结果集直接保存同一个 path 的引用,没有拷贝
- 重复元素没有排序就去重
- 没有剪枝,超时
面试官常见追问
- 回溯和 DFS 是什么关系?
- 怎么对有重复元素的情况去重?
- 组合和排列有什么区别,写法上有什么不同?
- 全排列的时间复杂度是多少?有重复元素时有几种?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。