最近有读者在准备算法面试问我说“组合总和”系列到底要刷到什么程度才算稳。我的建议是39、40、216这三道回溯题一定要能白板写出来而第四题“组合总和 Ⅳ”则是一次完全不同的考察方向。很多人都习惯性地把它当成回溯题去解结果在数据量一大时直接超时面试当场翻车。这道题在力扣上是第377题题面一句话就能说清给你一个由不同正整数组成的数组 nums和一个目标整数 target问有多少种不同的排列方式使得从 nums 中选出的数字之和恰好等于 target每个数字可以重复使用顺序不同视为不同方案。听起来像是组合计数实际上是一个典型的动态规划问题考察的核心是“排列计数”与“遍历顺序对结果的影响”。这篇博文就围绕这道题展开适合正在刷题准备面试的求职者也适合想彻底搞懂一维 DP 背包问题边界的人。1. 题目拆解这道题到底在考什么1.1 输入输出与规则确认我用一个简单例子帮大家把题意落实到纸面上。假设 nums [1, 2, 3]target 4那么所有合法方案一共有 7 种分别是1 1 1 11 1 21 2 12 1 11 33 12 2注意看1 3 和 3 1 会被当成两种不同方案因为它们排列顺序不一样。这就是本题和普通“组合总和”最大的区别组合问题只看集合不看顺序这里看的是排列顺序敏感。另外题目还给了两个隐含约束nums 中的所有元素都是正整数且各不相同。这两个约束不是废话它们直接决定了递推公式能不能用。如果数组里有 0那么目标值 i 会永远依赖 i - 0 产生无限循环DP 根本没法做如果数组里有重复元素那么“顺序不同视为不同方案”这个规则会和重复数字互相干扰结果会被虚增。所以面试时看到题面第一件事就是确认这两个约束。1.2 面试官出这道题的真实意图面试官在算法轮抛出这道题通常不是指望你背答案而是想观察三件事。第一你是不是只会套回溯模板。组合总和前几题都是回溯经典题很多人形成了肌肉记忆见“组合”两个字就写 DFS。但本题只要求输出方案数不要求枚举具体方案这种语义差异是选择算法的第一信号。第二你能不能区分“组合计数”和“排列计数”。这两个概念在背包 DP 里对应完全不同的遍历顺序。先遍历物品再遍历容量得到的是不考虑顺序的组合数先遍历容量再遍历物品得到的是考虑顺序的排列数。大部分候选人知道 dp[i] dp[i - num] 这个公式但说不清为什么这里必须先遍历容量这恰恰是面试官最想听到的深度。第三你处理边界和溢出的意识。虽然 LeetCode 原题说明答案保证在 32 位整数范围内但中间 dp 数组在 Java 里计算时仍然可能溢出。你有没有做保护用的什么类型这些都暴露了工程经验。2. 方案选型为什么回溯会在面试中翻车2.1 回溯不是不行只是不适合这道题先声明一个容易被误解的点回溯法并不是错误解对于小数据量它甚至更直观。比如你写一个标准 DFS枚举所有路径等于 target 时计数加一nums [1, 2, 3]target 4 时完全能跑通结果也是 7。但问题出在复杂度上。回溯搜索树的每一个节点最多有 n 个分支树的深度由 target 和最小元素共同决定。最坏情况下如果 nums 里包含 1那么深度就是 target整棵搜索树的节点数量级是 n 的 target 次方也就是 O(n^target)。这个复杂度有多恐怖target 30n 3运算量已经到 2 亿量级target 100n 4直接是天文数字。有些候选人会试图用剪枝优化比如当前累加值超过 target 就返回。这个剪枝在混合大小数字的数组里确实有效但最坏情况不会消失尤其是数组里全是小数字时剪枝基本等于没有。面试官追问“如果 target 从 4 改成 200你的代码还能跑吗”这题就挂了一半。2.2 从暴力递归到记忆化搜索如果面试官问你“回溯超时了怎么优化”你的思考路径应该是这样的既然枚举的是方案而方案数量庞大那能不能把重复计算的中间结果缓存起来观察递归过程。comb(remain) 表示“凑出剩余值 remain 的方案数”那么每次递归就是comb(remain) sum(comb(remain - num)其中 num 是 nums 中不大于 remain 的元素)你会发现comb(4) 会计算多次comb(3) 也会计算多次但这些结果完全固定。用一个哈希表或者数组把它们存下来下次直接返回这就是记忆化搜索。代码结构并不复杂class Solution { private int[] nums; private int[] memo; public int combinationSum4(int[] nums, int target) { this.nums nums; this.memo new int[target 1]; Arrays.fill(memo, -1); return dfs(target); } private int dfs(int remain) { if (remain 0) { return 1; } if (memo[remain] ! -1) { return memo[remain]; } int count 0; for (int num : nums) { if (remain num) { count dfs(remain - num); } } memo[remain] count; return count; } }记忆化搜索的时间复杂度是 O(target * n)空间复杂度是 O(target)已经达到了和动态规划一样的量级。面试中先给出这个版本再说“既然状态转移方向是确定的从小到大的剩余值先算就可以直接用数组递推不需要递归”这是非常自然的思路演进。3. 动态规划推导从爬楼梯到排列计数3.1 状态定义与转移方程把记忆化搜索的递归方向反转就是标准的自底向上动态规划。定义 dp[i] 表示“凑出总和 i 的方案数量”。对于任意一个 nums 中的元素 num只要 i 大于等于 num那么所有能凑出 i - num 的方案只要在末尾追加一个 num就能拼出一种凑出 i 的新方案。于是转移方程为dp[i] sum(dp[i - num])其中 num ∈ nums 且 num ≤ i边界条件 dp[0] 1表示“一个数都不选”时总和为 0 的方案数为 1。这个边界非常重要它既是递归的出口也是递推的起点。这个方程和爬楼梯问题的本质是一样的。爬楼梯是每次只能走 1 阶或 2 阶走到第 i 阶的方案数 dp[i] dp[i-1] dp[i-2]。本题只是把“台阶数”换成了“可选步长数组”从固定的 [1, 2] 变成任意的 nums所以很多教材也把它称为“进阶版爬楼梯”。3.2 遍历顺序决定你是“组合”还是“排列”这是全题最核心、也最容易被讲糊的地方。两类遍历方式代码如下// 排列数先遍历目标再遍历物品 for (int i 1; i target; i) { for (int num : nums) { if (i num) { dp[i] dp[i - num]; } } } // 组合数先遍历物品再遍历目标 for (int num : nums) { for (int i num; i target; i) { dp[i] dp[i - num]; } }为什么第二段代码得到的是组合数因为当 num 在外层循环时它在所有 dp[i] 的计算顺序中是被“固化”的。举个例子nums [1, 2, 3]在第二段代码里先处理数字 1再处理数字 2再处理数字 3。推导 dp[3] 时数字 3 只会在最后阶段参与它永远不可能出现在已经由数字 1、2 组成的序列的“中间位置”。于是 1 2 先出现2 1 永远无法产生因为处理数字 2 时你无法在一个已经包含 2 的方案里再插入一个 2 到前面。这就是组合数不计顺序的原因。第一段代码则不然。外层遍历每一个 i内层枚举最后一个数字。dp[3] 会分别从 dp[2] 加 1、dp[1] 加 2、dp[0] 加 3 三个方向累加。dp[2] 内部已经包含了“11”和“2”两种情况它们分别再追加 1就生成了“111”和“21”而 dp[1] 内部是“1”追加 2生成“12”。这样“21”和“12”都被完整保留下来了。面试时你不需要背这两段代码你只需要记一句话外层遍历目标容量枚举的是“最后一个数”所以能区分不同排列外层遍历物品枚举的是“物品使用的先后顺序”所以会丢失排列信息。3.3 边界条件与 dp[0] 的语义dp[0] 1 是很多人理解不透的地方。你可以从两个角度理解。第一个角度递归出口。在 DFS 里remain 0 时说明当前路径刚好凑满返回 1 表示找到一种方案。dp[0] 对应这个含义即不选任何元素也是一种合法的“空方案”。第二个角度转移方程的数学一致性。假设 nums [1], target 3那么 dp[1] dp[0] 1dp[2] dp[1] 1dp[3] dp[2] 1。如果 dp[0] 0那么所有结果都会变成 0整个递推直接坍塌。所以无论从递归还是递推看dp[0] 1 都是必须的。另外如果 target 本身就是 0根据题目语义空序列是一种合法方案结果直接返回 1。这个 corner case 虽然简单但很多人会忘记写。4. 代码实现与手推过程4.1 Java 实现与溢出处理先给一份可以直接运行的 Java 代码我在注释里标出了容易踩的坑。class Solution { public int combinationSum4(int[] nums, int target) { // dp[i] 表示凑出总和 i 的方案数 // 使用 double 避免中间结果溢出最后再转回 int double[] dp new double[target 1]; dp[0] 1; // 先遍历目标值再遍历 nums保证计算的是排列数 for (int i 1; i target; i) { for (int num : nums) { if (i num) { dp[i] dp[i - num]; } } } return (int) dp[target]; } }为什么不用 int 数组因为 Java 的 int 累加时dp[i - num] dp[i] 可能超过 Integer.MAX_VALUE即使最终答案满足 32 位范围中间过程也可能溢出。力扣官方题解里也提到过这一点给出的替代方案是用 float、double 或者 Long 类型。double 的精度对于 32 位整数范围内的计数完全够用转回 int 也不会有精度问题所以实战中我用 double 最省心。如果你面试时被要求必须用 int可以加一个溢出保护代码稍微繁琐一点public int combinationSum4(int[] nums, int target) { int[] dp new int[target 1]; dp[0] 1; for (int i 1; i target; i) { for (int num : nums) { if (i num dp[i - num] Integer.MAX_VALUE - dp[i]) { // 跳过会溢出的累加保证结果符合题目约束 continue; } if (i num) { dp[i] dp[i - num]; } } } return dp[target]; }这种写法看起来不够优雅但能体现你确实理解溢出发生的时机面试官通常也会认可。4.2 Python 实现Python 的 int 是任意精度天然没有溢出问题所以代码可以更干净class Solution: def combinationSum4(self, nums: List[int], target: int) - int: dp [0] * (target 1) dp[0] 1 for i in range(1, target 1): for num in nums: if i num: dp[i] dp[i - num] return dp[target]Python 版本的注意事项只有一个别把 nums 里的元素先排序再剪枝。排序本身不影响结果但如果你写了“num i 就 break”就必须先排序否则会漏掉后面还能用的数字。我见过不少人在 Python 版本里漏掉这个细节。4.3 手推一遍 dp 数组全过程以 nums [1, 2, 3]target 4 为例我们完整走一遍 DP 过程。初始化 dp [1, 0, 0, 0, 0]。计算 i 1num 1 时dp[1] dp[0]得到 dp[1] 1num 2 时i num跳过num 3 时i num跳过此时 dp[1] 1对应方案“1”。计算 i 2num 1 时dp[2] dp[1] 1num 2 时dp[2] dp[0] 1此时 dp[2] 2对应方案“11”和“2”。计算 i 3num 1 时dp[3] dp[2] 2num 2 时dp[3] dp[1] 1num 3 时dp[3] dp[0] 1此时 dp[3] 4对应方案“111”、“12”、“21”、“3”。计算 i 4num 1 时dp[4] dp[3] 4num 2 时dp[4] dp[2] 2num 3 时dp[4] dp[1] 1最终 dp[4] 7。把整个表格列出来面试时你可以直接画给面试官看idp[i] 的累加过程结果0初始化11dp[0]12dp[1] dp[0]23dp[2] dp[1] dp[0]44dp[3] dp[2] dp[1]7这张表能很直观地说明“每一个 dp[i] 都聚合了所有可能的最后一步”。5. 面试追问与变体识别5.1 面试官常问的四个进阶问题第一个追问“如果 nums 里有重复数字结果会怎样”这道题原题明确说了数字互不相同。但面试官可能会故意改条件。如果数组里有重复数字直接套用 DP 会把重复数字当成两个不同选择导致排列数量虚增。例如 nums [1, 1]target 2理论上有两种方案11 和 11但因为两个 1 完全等价实际只应该计 1 种。正确的处理方式是先对数组排序去重再去 DP。第二个追问“如果每个数字只能用一次呢”这时候问题就变成了一维 01 背包计数遍历顺序也变了。如果还是要求排列数状态会复杂得多因为每个数字的使用次数有上限通常需要压缩状态枚举排列面试很少会考到这么深。回答到“复杂度会完全不同需要状态压缩或者枚举排列”这个层面就够了。第三个追问“为什么 dp 数组只需要一维”因为 dp[i] 只依赖比 i 小的数也就是 dp[i - num]这些值在计算 dp[i] 之前已经全部确定不需要保存二维的历史版本。这一点和你用滚动数组优化二维完全背包是同样的道理。第四个追问“怎么继续优化时间复杂度”当前是 O(target * n)。如果 target 特别大nums 特别长可以先把大于 target 的数字过滤掉减少内层循环次数。如果 target 非常大但数字组合有规律也可以考虑用矩阵快速幂优化这个属于进阶玩法一般面试不要求。5.2 组合总和系列横向对比把整个系列放在一起看能帮你建立全局认知题目数组特点选择规则返回内容核心解法39 组合总和无重复数字可无限选所有组合回溯 剪枝40 组合总和 II有重复数字每个最多一次所有组合排序 回溯 去重216 组合总和 III1 到 9 固定集合k 个数总和 n所有组合回溯377 组合总和 IV无重复正整数可无限选方案总数动态规划注意 39、40、216 要枚举具体方案所以必须回溯377 只计数所以更适合 DP。如果面试官把 377 的返回条件改成“输出所有排列”那复杂度会爆炸一般不会这么考。5.3 口头表达建议面试白板写代码时我建议你用这样的口头表达顺序“我先定义 dp[i] 是凑出总和 i 的方案数。要凑出 i最后一个数字可以是 nums 里的任意一个 num所以把所有 dp[i - num] 加起来。因为最后一个数字不同就对应不同的排列所以外层循环要遍历 i内层遍历 num。dp[0] 等于 1表示空方案。边界处理完之后返回 dp[target]。”这样的表述能在 30 秒内把最核心的“为什么是先 target 再 nums”讲清楚面试官基本不会再追问遍历顺序问题。另外补充一个实战小技巧在白板写代码之前先问清楚“数字是否为正整数”“是否允许重复使用”“顺序不同是否算不同方案”。这三个问题的答案直接决定解法主动确认需求会给你加分哪怕你已经猜到了答案。6. 我在实际面试和刷题中踩过的坑这些坑我几乎每次教别人刷这道题时都会重新提一遍因为太典型了。第一个坑是写回溯时忘了加缓存。这道题用纯回溯在小数据量下能跑出正确结果很多初学者就以为“我的代码没问题”直到测试用例里 target 变成 35 以上才开始怀疑人生。强烈建议刷题时直接看限制条件如果 target 上限超过了 20就要主动往动态规划方向想。第二个坑是 Java 用 int 数组直接算。我见过有同学用 int 数组在本地跑力扣样例全过提交时发现报错原因就是中间结果溢出。解决办法就是前面说的 double 或者溢出判断。这个坑很隐蔽因为测试样例不会跑到特别大的边界你自测根本测不出来。第三个坑是混淆了 377 和力扣 518 零钱兑换 II。518 题是组合数返回的是“不考虑顺序”的方案数它的遍历顺序是先硬币后金额。有人把 518 的代码背得很熟拿到 377 直接套结果样例都过不了。这两个题挨得很近刷题时一定要放一起对比不然面试现场很容易混。第四个坑是忽略了“nums 中元素互不相同”这个条件。原题保证了互不相同但有些面试官喜欢现场改题问“如果有重复数字怎么办”。如果你没有提前思考过变体很容易卡住。我的建议是刷题时顺手把“重复数字”“不可重复使用”“数字可以为 0”这几种变体都推一遍这样无论面试官怎么改你都能接住。最后再分享一个小心得这道题表面上叫“组合总和”本质上是“排列计数”所以看题千万别被名字骗了。名字只是历史遗留的叫法算法选择要看题面描述里的“顺序不同视为不同方案”。我在面试别人时只要候选人能主动指出这一点哪怕代码写慢一点我也会给很高的评价因为这代表他真正理解了题目语义和算法模型的对应关系。