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