LeetCode LCR 104. 组合总和 Ⅳ
题目描述
题意分析
从互不相同的正整数
nums中取数，每个数可以使用任意多次，统计总和恰好为target的有序序列数量。顺序不同就算不同方案，无法凑出时返回 0。题目保证最终答案在 32 位整数范围内，要求精确计数，不需要取模。因为所有数都是正数，序列每增加一项，总和都会变大。
解法：按末尾元素统计有序方案
核心思路
[!blue]
定义
dp[i]为总和恰好为i的有序序列数。将这些序列按最后一个数num分类：去掉最后一项后，前缀的和就是i - num；反过来，给任意这样的前缀追加num，都能得到一个和为i的序列。因此对所有num <= i，累加dp[i - num]即可。每个序列的最后一项唯一，且候选值互不相同，各类计数不会重叠。初始化
dp[0] = 1，表示唯一的空序列；当i == num时，从这个空序列追加一项，就能正确计入单元素方案。正整数保证
i - num < i，所以从小到大枚举目标和时，全部前驱都已完成。外层是金额i，内层尝试每个末项；前驱本身已允许使用所有候选值，因此既支持重复取数，也保留了各种不同顺序。若交换为元素外层、金额内层，就会按固定的元素处理顺序构造方案，同一批元素的不同排列被合并。区别在于状态包含的选择范围，而不在于分类用首项还是末项：按首项分类，同样能推导出有序序列的这条递推。
对能够追加某个后缀到达
target的中间状态，它的每个前缀方案都能接上同一个后缀，得到不同的目标序列，所以这些相关状态的计数不会超过最终答案。其他状态不存在通向目标的转移链，即使计数超出整数范围，也不会影响目标的计算，现有代码无需擅自取模。负数进阶：若允许负数，按金额递增计算就失去了依赖顺序，而且可能存在总和为 0 的循环。若目标可达且存在这种循环，就能反复插入循环，产生无穷多种序列；含负数本身并不意味着所有输入都必然无穷。可以增加最大长度
L的限制，令f[len][sum]表示长度恰为len、总和为sum的方案数，从f[0][0] = 1按长度递推f[len][sum] = Σ f[len - 1][sum - num]，最后累计长度不超过L的目标状态。和可能为负，可用哈希表保存每层的有限状态。
解题步骤
- 创建长度为
target + 1的计数数组，设置dp[0] = 1。- 从 1 到
target递增枚举当前总和。- 遍历所有候选
num，若不超过当前总和，就累加对应的前驱计数。- 返回
dp[target]，不可达时它自然为 0。
代码实现
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
// 空序列是凑出 0 的唯一方案。
dp[0] = 1;
// 容量在外层、元素在内层：按「序列末位」分类，统计的是排列数。
for (int i = 1; i <= target; ++i) {
for (int num : nums) {
if (i >= num) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
func combinationSum4(nums []int, target int) int {
dp := make([]int, target+1)
// 空序列是凑出 0 的唯一方案。
dp[0] = 1
// 容量在外层、元素在内层：按「序列末位」分类，统计的是排列数。
for i := 1; i <= target; i++ {
for _, num := range nums {
if i >= num {
dp[i] += dp[i-num]
}
}
}
return dp[target]
}
复杂度分析
- 时间复杂度：$O(nT)$，其中 $n$ 为候选数个数、$T$ 为目标和，每个目标检查全部候选值。
- 空间复杂度：$O(T+1)$，保存各个总和的计数。
关键点总结
[!green]
- 每个序列唯一对应“较短序列加最后一项”，这是计数不重不漏的依据。
dp[0] = 1表示空前缀，不是把不可达金额记成一种方案。- 候选值互不相同，无需去重；同一个值可以在序列中反复出现。
- 负数进阶需要额外保证方案有限，限制序列长度后再按长度分层。
易错点总结
[!yellow]
- 将元素放在外层会改变计数含义，不能与本题金额外层的写法直接互换。
- 按首项分类仍可统计有序序列，不能把它误认为无序组合。
- 只有
i >= num时才能读取dp[i - num]。- 不能因遇到大计数就对任意模数取模，题目要求的是精确答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 39. 组合总和 | 中等 | 原题不区分组合内顺序，本题不同排列顺序分别计数，递推循环顺序需体现区别。 |
| 518. 零钱兑换 II | 中等 | 同样允许重复取数，硬币组合通常不计排列，本题按最后一项枚举有序方案。 |