组合总和 Ⅳ 图解题解

题目叫组合，为什么算的是排列

给数组 nums（无重复正整数）和目标 target，求和为 target 的方案数。名字叫「组合」，示例却拆穿它：nums = [1,2,3]、target = 6 时答案是 24，而 1+2 和 2+1 被算成两种。顺序不同即不同，本质是排列。

真正要数的是「有序的凑数序列」有多少条，摆错循环顺序就把排列数得成组合数。

为什么不能把所有序列枚举一遍

最笨的办法是把每条凑数序列都摆出来数，可分支数随 target 指数级膨胀，稍大就数不完。慢在重复：凑出总和 5 的序列，算总和 6、7 时又被反复重走。既然「凑出总和 t 的排列数」能独立回答，存下来复用即可。

dp 的下标是总和，值是排列数

定义 dp[t] 为「凑出总和 t 的排列数」。下标 t 是总和值不是位置，长度 target+1。

起点 dp[0] = 1，凑出总和 0 只有一种方案——一个数都不选的空序列。它是所有递推的源头，若误设成 0，整张表全归零，答案变 0。

转移为什么按最后一步分类相加

凑出 t 的每条排列，最后一个数总是确定的，就按这个末尾数分堆。末尾是 num 的那堆，把末尾去掉，剩下的正好是一条凑出 t−num 的排列，两者一一对应，所以这堆恰好有 dp[t−num] 条。对每个 num ≤ t 各分一堆，堆间不重、合起来不漏，于是 dp[t] = 各个 dp[t−num] 相加。

命门在循环顺序。这里外层遍历总和 t、内层遍历 nums，对每个 t 都把「末尾可以是任意一个 num」枚举一遍，同一个数在不同位置被反复计入，数出的是排列。LeetCode 518 零钱兑换 II 求组合数，循环正好反过来——外层遍历硬币、内层遍历金额，每种硬币只按固定次序出现，顺序被抹掉，得到组合。所以循环顺序不是细节：外层放谁，数出来就是谁。

手工演算：拿 nums=[1,2,3] 凑到 6

先铺 dp[0] = 1，往后每个 t 把 num ≤ t 的 dp[t−num] 加起来。

dp[1] = dp[0] = 1。dp[2] = dp[1] + dp[0] = 2。dp[3] = dp[2] + dp[1] + dp[0] = 2 + 1 + 1 = 4。dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7。dp[5] = dp[4] + dp[3] + dp[2] = 7 + 4 + 2 = 13。dp[6] = dp[5] + dp[4] + dp[3] = 13 + 7 + 4 = 24。

dp[6] = 24，即凑出 6 的全部排列数，和示例输出一致。

复杂度怎么算，循环写反和溢出两个坑

外层 target 个总和、内层扫 n 个数，时间 O(target×n)；只用一条 target+1 长的数组，空间 O(target)。

两个坑。一是循环顺序写反：外层遍历 nums、内层遍历 t，数出来是组合数而非排列数，会偏小。二是整数溢出：target 大时排列数会超出 32 位整数范围，C++/Java 要用 long 存 dp。

Python

class Solution:
    def combinationSum4(self, nums, target):
        dp = [0] * (target + 1)
        dp[0] = 1                       # 凑出 0 有空方案这一种
        for t in range(1, target + 1):  # 外层:总和 t
            for num in nums:            # 内层:最后取哪个 num
                if num <= t:
                    dp[t] += dp[t - num]    # 累加 dp[t-num]
        return dp[target]

C++

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned long long> dp(target + 1, 0);
        dp[0] = 1;                       // 空方案
        for (int t = 1; t <= target; t++) {       // 外层:总和
            for (int num : nums) {                // 内层:末尾数
                if (num <= t) dp[t] += dp[t - num];
            }
        }
        return (int) dp[target];
    }
};

Java

class Solution {
    public int combinationSum4(int[] nums, int target) {
        long[] dp = new long[target + 1];
        dp[0] = 1;                       // 空方案
        for (int t = 1; t <= target; t++) {       // 外层:总和
            for (int num : nums) {                // 内层:末尾数
                if (num <= t) dp[t] += dp[t - num];
            }
        }
        return (int) dp[target];
    }
}