最近有读者在准备算法面试，问我说“组合总和”系列到底要刷到什么程度才算稳。我的建议是：39、40、216这三道回溯题一定要能白板写出来，而第四题“组合总和 Ⅳ”则是一次完全不同的考察方向。很多人都习惯性地把它当成回溯题去解，结果在数据量一大时直接超时，面试当场翻车。

这道题在力扣上是第377题，题面一句话就能说清：给你一个由不同正整数组成的数组 nums，和一个目标整数 target，问有多少种不同的排列方式，使得从 nums 中选出的数字之和恰好等于 target，每个数字可以重复使用，顺序不同视为不同方案。听起来像是组合计数，实际上是一个典型的动态规划问题，考察的核心是“排列计数”与“遍历顺序对结果的影响”。这篇博文就围绕这道题展开，适合正在刷题准备面试的求职者，也适合想彻底搞懂一维 DP 背包问题边界的人。

1. 题目拆解：这道题到底在考什么

1.1 输入输出与规则确认

我用一个简单例子帮大家把题意落实到纸面上。假设 nums = [1, 2, 3]，target = 4，那么所有合法方案一共有 7 种，分别是：

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 2 + 1
• 2 + 1 + 1
• 1 + 3
• 3 + 1
• 2 + 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 = 30，n = 3，运算量已经到 2 亿量级；target = 100，n = 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] 内部已经包含了“1+1”和“2”两种情况，它们分别再追加 1，就生成了“1+1+1”和“2+1”；而 dp[1] 内部是“1”，追加 2，生成“1+2”。这样“2+1”和“1+2”都被完整保留下来了。

面试时你不需要背这两段代码，你只需要记一句话：外层遍历目标容量，枚举的是“最后一个数”，所以能区分不同排列；外层遍历物品，枚举的是“物品使用的先后顺序”，所以会丢失排列信息。

3.3 边界条件与 dp[0] 的语义

dp[0] = 1 是很多人理解不透的地方。你可以从两个角度理解。

第一个角度，递归出口。在 DFS 里，remain == 0 时说明当前路径刚好凑满，返回 1 表示找到一种方案。dp[0] 对应这个含义，即不选任何元素也是一种合法的“空方案”。

第二个角度，转移方程的数学一致性。假设 nums = [1], target = 3，那么 dp[1] = dp[0] = 1，dp[2] = dp[1] = 1，dp[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 = 1：

• num = 1 时，dp[1] += dp[0]，得到 dp[1] = 1
• num = 2 时，i < num，跳过
• num = 3 时，i < num，跳过

此时 dp[1] = 1，对应方案“1”。

计算 i = 2：

• num = 1 时，dp[2] += dp[1] = 1
• num = 2 时，dp[2] += dp[0] = 1

此时 dp[2] = 2，对应方案“1+1”和“2”。

计算 i = 3：

• num = 1 时，dp[3] += dp[2] = 2
• num = 2 时，dp[3] += dp[1] = 1
• num = 3 时，dp[3] += dp[0] = 1

此时 dp[3] = 4，对应方案“1+1+1”、“1+2”、“2+1”、“3”。

计算 i = 4：

• num = 1 时，dp[4] += dp[3] = 4
• num = 2 时，dp[4] += dp[2] = 2
• num = 3 时，dp[4] += dp[1] = 1

最终 dp[4] = 7。把整个表格列出来，面试时你可以直接画给面试官看：

这张表能很直观地说明“每一个 dp[i] 都聚合了所有可能的最后一步”。

5. 面试追问与变体识别

5.1 面试官常问的四个进阶问题

第一个追问：“如果 nums 里有重复数字，结果会怎样？”这道题原题明确说了数字互不相同。但面试官可能会故意改条件。如果数组里有重复数字，直接套用 DP 会把重复数字当成两个不同选择，导致排列数量虚增。例如 nums = [1, 1]，target = 2，理论上有两种方案：1+1 和 1+1，但因为两个 1 完全等价，实际只应该计 1 种。正确的处理方式是先对数组排序去重，再去 DP。

第二个追问：“如果每个数字只能用一次呢？”这时候问题就变成了一维 01 背包计数，遍历顺序也变了。如果还是要求排列数，状态会复杂得多，因为每个数字的使用次数有上限，通常需要压缩状态枚举排列，面试很少会考到这么深。回答到“复杂度会完全不同，需要状态压缩或者枚举排列”这个层面就够了。

第三个追问：“为什么 dp 数组只需要一维？”因为 dp[i] 只依赖比 i 小的数，也就是 dp[i - num]，这些值在计算 dp[i] 之前已经全部确定，不需要保存二维的历史版本。这一点和你用滚动数组优化二维完全背包是同样的道理。

第四个追问：“怎么继续优化时间复杂度？”当前是 O(target * n)。如果 target 特别大，nums 特别长，可以先把大于 target 的数字过滤掉，减少内层循环次数。如果 target 非常大但数字组合有规律，也可以考虑用矩阵快速幂优化，这个属于进阶玩法，一般面试不要求。

5.2 组合总和系列横向对比

把整个系列放在一起看，能帮你建立全局认知：

注意 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”这几种变体都推一遍，这样无论面试官怎么改，你都能接住。

最后再分享一个小心得：这道题表面上叫“组合总和”，本质上是“排列计数”，所以看题千万别被名字骗了。名字只是历史遗留的叫法，算法选择要看题面描述里的“顺序不同视为不同方案”。我在面试别人时，只要候选人能主动指出这一点，哪怕代码写慢一点，我也会给很高的评价，因为这代表他真正理解了题目语义和算法模型的对应关系。