组合总和 Ⅳ

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

给数组 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。