0377. Combination Sum IV¶
题目信息¶
- 题号:
0377
- 难度:
Medium
- 主题:
有序序列、目标和、可重复使用、方案计数
- 原题:
- 重点:
输入数字互不相同且均为正数、同一数字可重复使用、元素顺序不同算不同方案、答案保证适合 32 位整数
题目重述¶
给定由互不相同正整数组成的数组 nums 和正整数 target,统计有多少个有限有序序列,其每个元素都取自 nums,且所有元素之和恰好等于 target。数组中的同一个数可以在一个序列中使用任意多次。
元素排列顺序会区分方案,例如 [2,4,2] 与 [2,2,4] 是两个不同序列。nums 的长度位于 [1, 200],元素位于 [1, 1000],target 位于 [1, 1000]。测试数据保证最终方案数能够由 32 位有符号整数表示。
自建示例¶
相同元素组成不同顺序:
输入:nums = [2,4],target = 8
输出:5
解释:五个序列为 [2,2,2,2]、[2,2,4]、[2,4,2]、[4,2,2] 和 [4,4]。
无法组成目标:
输入:nums = [2,6],target = 5
输出:0
解释:所有可选数字都是偶数,任何有限序列的和也为偶数,无法得到 5。
按总和计数,最后一个元素区分顺序¶
定义 dp[sum] 为组成总和 sum 的有序序列数量。dp[0] = 1 表示空序列,构造 sum 时枚举最后放入的数字 num:此前的任意一个 sum - num 序列后面接上 num,都会得到一个不同序列,因此转移为 dp[sum] += dp[sum-num]。
先枚举总和、再枚举最后一个数字,而不是先固定数字再填表,正是把排列顺序区分开的原因;同一数字可重复使用,因为每个总和都可以再次从更小总和转移。
C++ 实现¶
class Solution {
public:
int combinationSum4(std::vector<int>& nums, int target) {
std::vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int sum = 1; sum <= target; ++sum) {
for (int num : nums) {
if (num <= sum) dp[sum] += dp[sum - num];
}
}
return dp[target];
}
};
代码分析¶
每个有序序列都有唯一的最后一个元素,转移既不重复计数也不漏掉方案;正数条件保证状态依赖严格变小,不会出现无限循环。时间复杂度为 O(target * nums.size()),额外空间为 O(target),答案范围由题目保证不会溢出。