LeetCode 377. Combination Sum IV：用 Go 动态规划解决排列型组合计数问题

LeetCode 377. Combination Sum IV：用 Go 动态规划解决排列型组合计数问题

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文以 leetcode/0377.Combination-Sum-IV/README.md 为主线，系统拆解 LeetCode 377 题（Combination Sum IV）的题目含义、暴力解法为何超时、动态规划状态转移方程的推导过程，并结合本仓库的 Go 实现 377. Combination Sum IV.go 与单元测试给出可运行的完整代码。读完本文，你将掌握「完全背包型计数问题」中排列与组合的本质区别，并能正确写出内外层循环顺序正确的 DP 代码。

题目回顾：数一数有多少种「排列」能凑出 target

题目原文（英文）要求如下：

Given an array ofdistinctintegersnumsand a target integertarget, returnthe number of possible combinations that add up totarget. The answer isguaranteedto fit in a32-bitinteger.

翻译成中文即是：给你一个由不同整数组成的数组nums和一个目标整数target，请从nums中找出并返回总和为target的元素组合的个数。题目数据保证答案符合 32 位整数范围。

需要注意的关键点是：本题虽然是 Combination Sum 系列的一员，但统计口径是排列——不同的顺序会被当作不同的答案。这与后文要对比的 518 题（Coin Change II）有着本质区别。

示例 1：顺序不同算不同答案

Input: nums = [1,2,3], target = 4 Output: 7 Explanation: The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations.

注意(1, 1, 2)、(1, 2, 1)、(2, 1, 1)三者在元素构成上完全相同，但因为排列顺序不同，被计为 3 种不同的答案，这正是本题与「组合」类题目的分水岭。

示例 2：凑不出来返回 0

Input: nums = [9], target = 3 Output: 0

当数组中没有任何元素能组成目标值时，答案自然为 0。

数据约束

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• 数组nums中所有元素互不相同（distinct）
• 1 <= target <= 1000

进阶追问（Follow up）

What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

即：如果数组中允许出现负数，问题会如何变化？需要增加什么限制才能让负数可行？这个问题我们会在本文最后一节给出完整推导。

暴力 DFS：思路直观，但必然超时

拿到题目后最直观的想法是回溯（DFS）：枚举每一步选择哪个数字，累加直到和等于target或超过target。原文档明确记录了作者的第一次尝试：

笔者先用暴力解法 dfs 尝试了一版，包含的重叠子问题特别多，剪枝条件也没有写好，果然超时。

仓库中的 377. Combination Sum IV.go 完整保留了这版超时实现：

// 暴力解法超时 func combinationSum41(nums []int, target int) int { if len(nums) == 0 { return 0 } c, res := []int{}, 0 findcombinationSum4(nums, target, 0, c, &res) return res } func findcombinationSum4(nums []int, target, index int, c []int, res *int) { if target <= 0 { if target == 0 { *res++ } return } for i := 0; i < len(nums); i++ { c = append(c, nums[i]) findcombinationSum4(nums, target-nums[i], i, c, res) c = c[:len(c)-1] } }

这段代码的核心缺陷在于：它本质上是在枚举整棵搜索树的所有路径，而排列的数量是指数级爆炸的。原文档给出了一个极具冲击力的数据点：

元素只有 [1,2,3] 这三种，target = 32，这组数据居然有 181997601 这么多种情况。

也就是说，即使nums只有 3 个元素，当target = 32时答案就高达1.8 亿。如果采用 DFS 逐条枚举，时间复杂度与答案规模成正比，在target = 1000的极限数据下（nums.length最大可达 200），任何机器都无法在时限内跑完。

此外，从代码中还能看到大量重叠子问题：例如在递归过程中，target - nums[i]这一中间状态会被无数次重复计算，而 DFS 没有记忆化，只能一遍遍重新枚举。这两点叠加，超时是必然的。

也正因如此，测试文件 377. Combination Sum IV_test.go 中对暴力解法做了特殊处理——只在target <= 4的小输入下调用combinationSum41做交叉验证，避免在target = 32时把测试跑挂：

// 暴力解法在 target 较大时超时，仅对小输入调用以覆盖代码。 if p.k <= 4 { if got := combinationSum41(p.n, p.k); got != a.one { t.Fatalf("combinationSum41(%v, %v) = %v, want %v", p.n, p.k, got, a.one) } }

动态规划解法：O(n·target) 的计数 DP

既然 DFS 不可行，结合题目数据规模（target <= 1000）基本可以断定：此题是动态规划，且时间复杂度在O(n^2)量级（即O(len(nums) × target)）。

状态定义

定义dp[i]为「总和等于i的排列总数」。最终答案存放在dp[target]中。

边界条件

dp[0] = 1：表示不取任何数字、总和为 0 时，存在 1 种「空排列」。这是所有递推的起点。

状态转移方程

原文档给出了如下方程：

$$dp[i] =\left{\begin{matrix}1,i=0\ \sum dp[i-j],i\neq 0\end{matrix}\right.$$

其中j遍历nums中的所有元素，并且只在i - j >= 0时累加dp[i-j]。直观理解是：任何总和为i的排列，都可以看作「总和为i-j的某个排列」在末尾追加一个元素j得到。由于排列的最后一个位置可以放任意一个j，因此对j求和即可。

Go 实现

仓库 377. Combination Sum IV.go 中的最终实现如下：

package leetcode func combinationSum4(nums []int, target int) int { dp := make([]int, target+1) dp[0] = 1 for i := 1; i <= target; i++ { for _, num := range nums { if i-num >= 0 { dp[i] += dp[i-num] } } } return dp[target] }

逐行解读：

1. dp := make([]int, target+1)：开一个长度为target+1的数组，下标即「当前总和」；
2. dp[0] = 1：初始化边界；
3. 外层循环for i := 1; i <= target; i++遍历「金额」，从小到大逐个计算dp[1]到dp[target]；
4. 内层循环遍历nums中的每个数字num，只要i-num >= 0（说明可以用num作为某个排列的最后一个元素），就把dp[i-num]累加到dp[i]；
5. 最终返回dp[target]。

复杂度分析

• 时间复杂度：O(len(nums) × target)，两层循环嵌套，target <= 1000、len(nums) <= 200，最坏约 20 万次运算，轻松通过；
• 空间复杂度：O(target)，仅需要一个一维数组。

为什么外层遍历「金额」、内层遍历「元素」？

这是本题最容易写错的地方，也是与 518 题（Coin Change II）最关键的差异。我们可以对比仓库中 518. Coin Change II.go 的实现：

func change(amount int, coins []int) int { dp := make([]int, amount+1) dp[0] = 1 for _, coin := range coins { for i := coin; i <= amount; i++ { dp[i] += dp[i-coin] } } return dp[amount] }

对比可见：

原因在于：外层遍历金额时，dp[i]会枚举「以任意元素收尾」的全部可能，天然保留排列顺序信息；而外层先固定元素（类似完全背包「先遍历物品」），等价于限定了元素的加入顺序，把同一组元素的不同排列合并成一种组合，从而避免重复计数。这一点在 518 题的 README.md 中也有明确说明：

在计算dp[i]的值时，可以确保金额之和等于i的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。

测试用例验证：三组数据全部通过

仓库测试文件 377. Combination Sum IV_test.go 定义了三个用例：

qs := []question377{ { para377{[]int{1, 2, 3}, 4}, ans377{7}, }, { para377{[]int{1, 2, 3}, 32}, ans377{181997601}, }, { para377{[]int{}, 4}, ans377{0}, }, }

三组用例分别覆盖了三种典型场景：

1. 常规场景：nums = [1,2,3], target = 4，期望输出7，与题目示例一致；
2. 大数据量场景：nums = [1,2,3], target = 32，期望输出181997601——这组数据正是原文档中用来证明「暴力 DFS 必然超时」的例证，同时也验证了 DP 解法在结果巨大时依然瞬时完成，并校验了 32 位整数范围内的正确性；
3. 空数组边界：nums = [], target = 4，期望输出0——当可选集合为空时，任何正target都无法凑出，答案恒为 0（DP 循环自然给出 0，无需特判）。

运行go test即可验证上述用例全部通过，这也是仓库所宣称的「100% test coverage」在本题上的具体体现。项目根目录下的 gotest.sh 提供了批量跑测试的脚本入口，go.mod 声明了module github.com/halfrost/LeetCode-Go与go 1.19的最低版本要求。

Follow up 深度解析：为什么不允许负数？

原文档末尾提出了一个极具启发性的进阶问题：如果nums中出现负数，问题会发生什么变化？

核心结论是：一旦允许负数，答案可能变成无限大，题目将不再有有限解。原文档给出的推导如下：

假设数组nums中含有正整数a和负整数−b（其中a>0, b>0, -b<0），则有a×b + (−b)×a = 0。

这句话的含义是：任意一个元素之和等于target的排列，都可以在其末尾追加b个a和a个−b，得到一个新的、和仍为target的排列。具体而言，在排列末尾追加：

• b个a，贡献b × a；
• a个−b，贡献a × (−b) = −a×b；

两者相加恰好为 0，不影响总和，但生成了一个新的、更长的合法排列。而新排列末尾依然可以继续追加b个a和a个−b，如此反复，可以无限构造出越来越长的排列。

因此只要存在至少一个和为target的排列，就能构造出无限长度的排列序列，答案自然趋于无穷大，DP 计数失去意义。

要允许负数，需要加什么限制？

根据上述推导，要想让含负数的版本重新变得可解，必须破坏「无限拼接」的可能，常见做法是：

• 限制排列的最大长度：例如规定排列最多包含k个元素，把搜索空间限定在有限范围内，此时可以用带「长度维度」的 DP（如dp[i][l]表示和为i、长度为l的排列数）；
• 或限制每个元素的使用次数，使可构造的排列总数有限。

原文档明确给出的答案是前者：如果允许负数出现，则必须限制排列的最大长度，不然会出现无限长度的排列。这是本题在面试追问环节最常考察的点，理解「a×b + (−b)×a = 0」这一构造性证明是回答关键。

系列关联：Combination Sum 家族与计数 DP

本题属于 Combination Sum 系列问题，仓库中收录了多个同族题目，可对照学习：

其中 518 题的 README.md 末尾特别指出「和此题完全一致的解题思路的题有，第 377 题和第 494 题」，可见这三题共享同一套「完全背包型计数 DP」方法论，区别只在于循环顺序决定了统计的是排列还是组合。建议将三题放在一起刷，对比它们的循环结构差异，即可彻底掌握这类题目。

小结

LeetCode 377（Combination Sum IV）是一道经典的「排列型完全背包计数」问题：

• 暴力 DFS 不可行：排列数量指数级爆炸，target = 32时答案已达 1.8 亿，重叠子问题众多；
• DP 是关键：定义dp[i]为总和为i的排列数，状态转移为dp[i] = Σ dp[i-num]，外层遍历金额、内层遍历元素，时间复杂度O(len(nums) × target)，空间复杂度O(target)；
• 与 518 题对比记忆：外层遍历元素得到的是组合数，外层遍历金额得到的是排列数；
• 负数 Follow up：允许负数会导致无限长度排列（a×b + (−b)×a = 0可无限拼接），必须限制排列最大长度才能重新可解。

仓库中的完整实现与测试代码位于 leetcode/0377.Combination-Sum-IV/，可直接作为参考与验证。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go