数字可重复选取,如何输出凑出 target 的全部组合?
哪些公司问过
答案要点
- 回溯:记录起始下标、剩余值和当前路径,剩余为 0 时保存结果
- 可重复选取时递归传入当前下标 i,而不是 i+1
- 只从起始下标往后选,保证组合不重复(不会同时出现 [2,3] 和 [3,2])
- 排序后遇到大于剩余值的数直接 break 剪枝
- {2,3,4,5} 凑 7 的结果为 [2,2,3]、[2,5]、[3,4]
易错点
- 递归传 i+1,导致每个数只能用一次
- 每层都从 0 开始枚举,产生顺序不同的重复组合
- 把 path 直接加入结果而不拷贝,回溯后结果被修改
面试官常见追问
- 如果每个数只能用一次,且数组有重复元素呢?
- 如果只求组合的数量,不输出具体组合呢?
- 如果顺序不同算不同方案呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。