面试题库 › Java 后端 › 组合总和:元素可重复使用(LC39)

组合总和:元素可重复使用(LC39)

难度 ★★☆在 2 场真实面经中被问到 方向:Java 后端考点:贪心与回溯

哪些公司问过

美团1字节跳动1

常见岗位:Java 后端、嵌入式软件

答案要点

  1. 回溯:枚举候选数加入路径,递归后撤销选择
  2. 可重复使用:递归下一层从当前下标 i 开始,而不是 i+1
  3. 去重组合:每层从 start 开始,保证组合内元素非递减
  4. 剪枝:排序后当前数大于剩余目标时直接 break
  5. 只求个数可用完全背包 DP,dp[j] += dp[j-num],时间 O(N·T)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题