组合(LeetCode 77)回溯与剪枝
哪些公司问过
答案要点
- 回溯:path 长度为 k 时记录结果,否则从 start 到 n 依次选择,递归起点为 i+1
- 剪枝:i ≤ n - (k - path.size()) + 1,剩余数字不足时提前结束
- 时间约 O(C(n,k)·k),额外空间 O(k)(不含结果)
- 有重复元素时先排序,同一层跳过相同元素去重
- 加入结果时要拷贝路径,避免后续回溯修改
易错点
- 直接把 path 引用加入结果,回溯后结果被清空
- 递归起点写成 start+1 而不是 i+1,产生重复组合
- 没有剪枝,n 较大时搜索大量无效分支
面试官常见追问
- 时间复杂度和空间复杂度是多少?
- 还有非递归写法吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。