今日面试算法推荐组合总和LeetCode 39一、题目概述题目描述给定一个无重复元素的整数数组candidates和一个目标数target找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复被选取。示例输入candidates [2, 3, 6, 7], target 7 输出[[2, 2, 3], [7]]核心特点数组元素均为正整数递归搜索时剩余目标值严格递减不会出现死循环解集不能包含重复组合[2, 2, 3]和[3, 2, 2]视为同一组合每个数字可无限次使用这是动态规划解法能套用完全背包模型的前提二、五种解法全解析这道题之所以被面试官青睐是因为一道题能聊出五种以上的解法每种解法背后都代表一类经典算法思路 。解法核心思想时间复杂度面试推荐度标准回溯法枚举所有可能O(2^target)⭐⭐⭐排序剪枝回溯回溯提前终止O(2^target)⭐⭐⭐⭐⭐动态规划完全背包模型O(n×target)⭐⭐⭐⭐记忆化搜索带备忘录的DFSO(n×target)⭐⭐⭐⭐显式栈迭代手动模拟递归O(2^target)⭐⭐⭐三、核心代码实现1. 标准回溯法面试首版代码def combinationSum(candidates, target): res [] n len(candidates) def dfs(start, remain, path): # 剩余和为0当前路径就是一组答案 if remain 0: res.append(path[:]) # 注意必须复制path return for i in range(start, n): path.append(candidates[i]) dfs(i, remain - candidates[i], path) path.pop() # 回溯撤销选择恢复状态 dfs(0, target, []) return res关键要点收集答案时必须res.append(path[:])因为path是同一个列表对象后续递归会修改其内容使用start参数保证搜索方向避免生成重复组合2. 排序剪枝回溯面试推荐正解def combinationSum(candidates, target): candidates.sort() # 关键排序后才能剪枝 res [] n len(candidates) def dfs(start, remain, path): if remain 0: res.append(path[:]) return for i in range(start, n): if candidates[i] remain: # 剪枝当前数已超剩余和 break path.append(candidates[i]) dfs(i, remain - candidates[i], path) path.pop() dfs(0, target, []) return res优化效果排序后当candidates[i] remain时后续所有数字都必然超过剩余和可直接break终止当前分支。3. 动态规划解法完全背包模型def combinationSum_dp(candidates, target): dp [[] for _ in range(target 1)] dp[0] [[]] # 关键和为0有一个空组合 for c in candidates: for t in range(c, target 1): for combo in dp[t - c]: dp[t].append(combo [c]) return dp[target]适用场景适合回答组合数量类变体问题将选数凑和看成完全背包填容量。四、面试官追问方向根据搜索结果面试官围绕这道题可能进行以下层层追问 基础层能否写出正确的回溯代码优化层如何剪枝减少无效搜索变体层如果candidates有重复元素怎么办LeetCode 40如果只问组合数量、不问具体内容DP计数如果把组合改成排列遍历顺序变化深度层能否用非递归方式实现显式栈迭代五、学习建议今日学习路径时间段学习内容目标30分钟理解回溯法核心三要素选择、约束、撤销能独立写出标准回溯代码30分钟掌握排序剪枝优化技巧理解剪枝如何减少搜索空间30分钟对比动态规划解法理解同一问题的不同建模视角30分钟手动模拟 n4 的执行过程验证代码逻辑正确性延伸练习LeetCode 40组合总和 II元素只能用一次LeetCode 216组合总和 III限定组合长度N皇后问题回溯法进阶经典六、高频算法知识地图根据搜索结果面试算法可归纳为五大解题范式┌─────────────────────────────────────────────────────┐ │ 面试算法五大解题范式 │ ├─────────────────────────────────────────────────────┤ │ 暴力枚举 → 分治与递归 → 贪心 → 动态规划 → 回溯 │ └─────────────────────────────────────────────────────┘ ↓ ┌─────────────────────────────────────────────────────┐ │ 五大优化技巧降维打击 │ ├─────────────────────────────────────────────────────┤ │ 双指针 | 滑动窗口 | 前缀和 | 二分 | 位运算 │ └─────────────────────────────────────────────────────┘必考级别数组/字符串的双指针、滑动窗口、前缀和链表的反转与合并哈希表的两数之和、异位词分组二叉树的递归遍历与层序二分搜索、快速排序与归并排序动态规划的爬楼梯、打家劫舍、背包问题回溯的全排列、组合建议学习建议继续学习N皇后问题LeetCode 51这是回溯法的进阶经典题可延伸出位运算压缩、对称性剪枝等高级优化技巧 。参考来源【2026大厂AI岗位面试真题】Agent开发岗含完整答案- 后端与系统基础 手撕算法附 Causal Mask、Agent Loop 手写-CSDN博客组合总和五种解法回溯、剪枝、动态规划与记忆化搜索全解析-CSDN博客2026 年 AI 面试工具「高管/资深岗位」选型指南6 款产品在 8 年经验面试中的-CSDN博客数据结构与算法面试速刷手册考点地图代码模板高频题清单-CSDN博客2026 年 AI 面试工具「社招技术岗」选型指南6 款产品在 3-5 年经验后端面试中的实测-CSDN博客N皇后问题五种解法从回溯到位运算剪枝全解析-CSDN博客