LeetCode 377. 组合总和 Ⅳ

2022-08-04 HGNULB 约 7 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 377. 组合总和 Ⅳ

题意分析

输入是一个元素互不相同的正整数数组和一个目标值 target，要统计有多少种取数方案使得总和恰好为 target，其中每个数可以被重复取用，并且题目明确说明「顺序不同的序列算作不同方案」。

约束给得很小：nums 长度不超过 200，每个元素不超过 1000，target 不超过 1000。这个规模意味着允许把 1 到 target 之间的每个中间和都单独算一遍，不必追求更巧的公式。

「元素互不相同」这一条免去了重复计数的麻烦，「元素全为正数」则保证累计和只会单调变大，不会出现绕回去的情况，这两点都是后面推理能成立的前提。

边界要留意两处：target 可能比数组里所有元素都小，这时答案是 0；题目只保证最终答案落在 32 位整数内，并没有保证推导途中的量也落在里面。

题目末尾的进阶问「如果允许负数会怎样」，反过来提醒了正数这个前提有多关键。

解法：按目标和递推的一维 DP

核心思路

最直接的想法是把每种取数序列都摆出来：从空序列开始，每次从 nums 里挑一个数接在后面，和超过 target 就剪掉，和正好等于 target 就计一次。问题是方案数本身就是指数级的，nums = [1,2,3]、target = 1000 时根本枚举不完。

瓶颈在于重复劳动。两个不同的前缀，只要当前累计和相同，后面能补出多少种续法就完全一样，但逐条展开的做法会把每个前缀都单独走一遍。

顺着这一点，把关注对象从「序列长什么样」换成「已经凑到多少」。把任意一个合法序列按最后一个数切开：若最后一位是 num，那前面那截恰好是一个和为 target - num 的合法序列，而且这种切分方式唯一，既不重也不漏。

于是状态定义为：dp[s] 表示和恰好为 s 的有序方案数。转移是 $dp[s] = \sum_{num \le s} dp[s - num]$，边界 dp[0] = 1，表示空序列是凑出 0 的唯一方案。

状态里之所以不需要「用过哪些数」这一维，正是因为题目按顺序区分方案：只要固定最后一位，剩下的部分就是一个规模更小的同类问题，与前面具体用了什么无关。

解题步骤

开一个长度为 target + 1 的数组 dp，并令 dp[0] = 1。长度多出的 1 是为了能容纳下标 target；而 dp[0] 是所有转移的种子，它若为 0，整个数组都会保持 0。

让 s 从 1 递增到 target 作为外层循环。之所以必须递增，是因为转移要读 dp[s - num]，而 s - num 严格小于 s，只有按 s 从小到大算才能保证被引用的状态已经确定。

对每个 s，内层遍历 nums 中的每个 num，仅在 num <= s 时执行 dp[s] += dp[s - num]。这个判断一方面防止下标为负，另一方面对应「最后一位放不下 num」的真实含义。

内层遍历数字而不是把数字放到外层，是因为每个 dp[s] 必须一次性收齐「最后一位取任意 num」的全部情况。反过来把数字放外层，等价于给数字定了一个固定使用次序，统计出来的就是不计顺序的组合数。

返回 dp[target]。Java 里用 long 存 dp、返回时再强转 int，是为了让中间累加不受 32 位溢出干扰。

以 nums = [1,2,3]、target = 4 走一遍：初始 dp = [1, 0, 0, 0, 0]。s = 1 时只有 num = 1 可用，dp[1] = dp[0] = 1。s = 2 时 num = 1 贡献 dp[1] = 1，num = 2 贡献 dp[0] = 1，累加得 dp[2] = 2。s = 3 时 num = 1 贡献 dp[2] = 2，num = 2 贡献 dp[1] = 1，num = 3 贡献 dp[0] = 1，累加得 dp[3] = 4。s = 4 时 num = 1 贡献 dp[3] = 4，num = 2 贡献 dp[2] = 2，num = 3 贡献 dp[1] = 1，累加得 dp[4] = 7。最终数组为 [1, 1, 2, 4, 7]，返回 7，正对应题面列出的七种序列。

代码实现

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(target \cdot n)$，其中 n 为 nums 长度；一共 target 个状态，每个状态把 nums 完整扫一遍，除此之外没有别的开销。

空间复杂度：$O(target)$，只有一维 dp 数组，长度为 target + 1，没有递归栈也没有额外容器。

关键点总结

「顺序不同算不同方案」是这道题的分水岭：它既决定了状态里不必记录用过哪些数，也决定了两层循环谁在外面。

按「最后一步选了什么」切分方案，是计数型动态规划最通用的建模手法；切分唯一，就自动保证了不重不漏。

dp[0] = 1 不是凑出来的常数，它表达的是「空序列」这个真实存在的方案，把边界翻译回题意能挡掉大半初始化错误。

一维数组按下标递增填表时，只要转移只引用更小的下标，就天然满足「被依赖的状态已算好」，不需要额外的滚动技巧。

面试视角：被追问「和 518. 零钱兑换 II 差在哪」时要能立刻说清，那题求组合数、循环是数字在外容量在内，本题求排列数、顺序正好相反；同时主动提一句中间量溢出的风险，Java 用 long 存 dp 是几乎零成本的保险。

易错点总结

错误写法：把两层循环写成数字在外、目标和在内 → nums = [1,2]、target = 3 时只统计到 (1,1,1) 和 (1,2)，返回 2，丢掉了 (2,1)，因为这种顺序算的是组合数。

错误写法：忘记 dp[0] = 1，让数组保持全 0 → 任何输入都返回 0，而且过程中看不出任何异常。

错误写法：内层不判断 num <= sum 就直接累加 dp[sum - num] → nums = [5]、target = 3 时下标为 -2，直接数组越界。

错误写法：转移写成 dp[sum] = dp[sum - num] + 1 → nums = [1,2,3]、target = 3 时得到 2，而正确答案是 4；这种写法把「方案数」偷换成了「长度」，小样例上偶尔碰巧对，稍大就全错。

错误写法：Java 里用 int[] 存 dp → 题目只保证最终答案在 int 范围内，中间某个 dp[s] 一旦越界就会翻成负数，最后返回一个负的方案数。

错误写法：没排序就在内层写 if (num > sum) break → nums = [3,1] 时 s = 1 遇到 3 立刻跳出，num = 1 的转移被跳过，dp[1] 停在 0，后面全塌。

错误写法：数组开成 new long[target] → 最后访问 dp[target] 越界，长度必须是 target + 1。

错误写法：被问到进阶「允许负数怎么办」时回答照旧递推 → 有负数后 1 和 -1 可以无限互相抵消，方案数是无穷的，必须额外限制序列长度才谈得上计数。

相似题目

题目	难度	考察点
279. 完全平方数	中等	物品集合是平方数，求最少个数
322. 零钱兑换	中等	求最少硬币数，需处理不可达状态
518. 零钱兑换 II	中等	求组合数，循环顺序与本题相反
1449. 数位成本和为目标值的最大数字	困难	恰好装满后还要构造字典序最大解
LCR 103. 零钱兑换	中等	与 322 同题，练最少个数型转移
LCR 104. 组合总和 Ⅳ	中等	与本题同题，可用来复核循环顺序
面试题 08.11. 硬币	中等	组合数且需要边算边取模