LeetCode 377. 组合总和 Ⅳ
题目描述
题意分析
从互不相同的正整数中选取若干项，使总和等于
target，返回不同有序序列的数量。每个数可以重复使用，选中值相同但先后顺序不同也分别计数，因此这里虽然叫组合，实际统计的是有序方案。目标为正数，无法凑出时返回零，题目保证最终答案处于 32 位整数范围内。题面关于负数的进阶会改变有限性和状态依赖，不能直接把负数放进现有递推。
解法：按目标和递推的一维 DP
核心思路
[!blue]
用
dp[sum]表示总和恰好为sum的有序序列数量。按最后一项分类：若末项选择num，删去它后，前面的序列必须凑出sum - num，共有dp[sum - num]种；在每条前缀后追加这个末项，又唯一地得到一条完整序列。不同末项形成的类别互不重复，所有完整序列又都有唯一末项，因此将全部
num <= sum对应的前缀数量相加，就得到当前状态。某个前缀可以已经用过同样的数字，所以重复使用也被自然涵盖。候选均为正数，
sum - num严格小于sum，因此从小到大计算目标和时，依赖状态都已完成。总和在外层，内层枚举所有末项，才能让每个状态包含各种排列顺序；把数字放外层会限制加入顺序，变成另一种不计排列的统计。初始化
dp[0] = 1，表示空前缀的一种选择。它使恰好用一个数凑出当前和时能贡献一条序列；若设为零，所有后续状态都失去起点。其他状态从零开始，只累加能够接上的前缀。进阶允许正负数混用时，可以反复加入和为零的非空片段，导致某些目标拥有无限多条序列；依赖也可能回到更大的和，当前按和递增的填表顺序不再成立。需要增加限制，例如序列长度不超过
L。有了长度上限，可定义
ways[len][sum]为恰用len项凑出sum的数量，从ways[0][0] = 1开始，每层给已有和追加任意候选并写入下一长度层，最后累计长度一到L中目标和的计数。用哈希表保存实际可达的和即可；中间和可能为负或暂时超过目标，不能按原来0..target的范围截掉。长度严格增加保证状态无循环、方案有限。
解题步骤
- 为基础题建立
dp[0..target]，令dp[0] = 1，其余为零。- 按
sum = 1..target依次计算，内层枚举每个候选num。- 只有
num <= sum时，才将dp[sum - num]加入dp[sum]。- 返回
dp[target]；若没有任何可行前缀，计数自然保持零。
代码实现
class Solution {
// dp[sum] 表示凑出和为 sum 的有序方案数，最后一个数字可以是任意 num <= sum。
public int combinationSum4(int[] nums, int target) {
long[] dp = new long[target + 1];
// 空序列提供凑零的一种起始方案
dp[0] = 1;
// 和在外层，按最后一项分类统计不同顺序
for (int sum = 1; sum <= target; sum++) {
for (int num : nums) {
if (num <= sum) {
dp[sum] += dp[sum - num];
}
}
}
return (int) dp[target];
}
}
func combinationSum4(nums []int, target int) int {
// dp[sum] 表示凑出和为 sum 的有序方案数，最后一个数字可以是任意 num <= sum。
dp := make([]int, target+1)
// 空序列提供凑零的一种起始方案
dp[0] = 1
// 和在外层，按最后一项分类统计不同顺序
for sum := 1; sum <= target; sum++ {
for _, num := range nums {
if num <= sum {
dp[sum] += dp[sum-num]
}
}
}
return dp[target]
}
复杂度分析
- 时间复杂度：$O(Tn)$，
T为目标和，n为候选数字数。- 空间复杂度：$O(T+1)$，一维计数表。
关键点总结
[!green]
- 每个序列最后一项唯一，因此分类不重不漏。
- 循环顺序决定统计有序排列还是不计顺序组合。
- 能继续凑到最终目标的中间状态，可为每个序列追加同一段补全序列，因此其计数不超过最终答案；不能仅凭最终范围就断言所有无关状态都不会溢出。
易错点总结
[!yellow]
- 数字放在外层会改变顺序的统计方式，不能与按最后一项分类的状态含义混用。
- 空前缀应有一种选择，将
dp[0]设为零会让全部递推为零。- 未检查
num <= sum就转移，会读取负下标。- 允许负数后仍沿用按和递增的一维表，既忽略循环依赖，也没有解决可能出现的无限方案。
- 仅保证最终答案范围，并不意味着所有不相关的中间状态都同样小；不能据此作出更强的范围承诺。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 39. 组合总和 | 中等 | 原题不区分组合内顺序，本题不同排列顺序分别计数，递推循环顺序需体现区别。 |
| 518. 零钱兑换 II | 中等 | 同样允许重复取数，硬币组合通常不计排列，本题按最后一项枚举有序方案。 |
| 322. 零钱兑换 | 中等 | 按金额或目标长度累积可重复选择的结果；本题先枚举目标以统计有序方案，该题求最少硬币数。 |
| 279. 完全平方数 | 中等 | 按金额或目标长度累积可重复选择的结果；本题先枚举目标以统计有序方案，该题候选值为完全平方数。 |
| 40. 组合总和 II | 中等 | 组合总和系列。IV 允许重复使用且按排列计数；II 每个位置只用一次，枚举并去重无序组合。 |
| 216. 组合总和 III | 中等 | 组合总和系列。III 增加固定取数个数和 1 到 9 的范围限制，回溯状态还要记录剩余数量。 |