组合总和:元素可重复使用(LC39)
哪些公司问过
答案要点
- 回溯:枚举候选数加入路径,递归后撤销选择
- 可重复使用:递归下一层从当前下标 i 开始,而不是 i+1
- 去重组合:每层从 start 开始,保证组合内元素非递减
- 剪枝:排序后当前数大于剩余目标时直接 break
- 只求个数可用完全背包 DP,dp[j] += dp[j-num],时间 O(N·T)
易错点
- 递归下一层传 i+1,导致元素不能重复使用
- 每层从 0 开始枚举,产生 [2,3] 和 [3,2] 这样的重复组合
- 求个数的 DP 把两层循环写反,算成了排列数
面试官常见追问
- 如果每个数只能用一次且数组有重复(LC40)怎么改?
- 只求组合个数时 DP 怎么写?
- 为什么加入结果时要拷贝 path?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。