中文题目
给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3 输出：0
提示：
1 <= nums.length <= 2001 <= nums[i] <= 1000nums中的所有元素 互不相同1 <= target <= 1000
进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
注意：本题与主站 377 题相同：https://leetcode-cn.com/problems/combination-sum-iv/
通过代码
高赞题解
我总结了剑指Offer专项训练的所有题目类型，并给出了刷题建议和所有题解。
在github上开源了，不来看看吗？顺道一提：还有C++、数据结构与算法、计算机网络、操作系统、数据库的秋招知识总结，求求star了，这对我真的很重要？
$\Rightarrow$通关剑2
解题思路
这道题一看，似乎是完全背包诶。
物品就是nums的元素并且可以无限次选取，然后需要刚好凑到target大小的背包才行。
背包问题技巧：
0-1背包，即数组中的元素选取0次或者1次
有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。
定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：
- 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，
dp[i][j] = dp[i-1][j]。 - 第 i 件物品添加到背包中，
dp[i][j] = dp[i-1][j-w] + v。
第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);空间优化
在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，
dp[j] = max(dp[j], dp[j - w] + v);因为 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w]，防止将 dp[i-1][j-w] 覆盖。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]，在程序实现时需要按倒序来循环求解。
0-1背包循环顺序
0-1背包中二维dp数组的两个for遍历的先后循序是可以颠倒
dp[i][j] 表示
- 前 i 件物品
- 体积不超过 j
能达到的最大价值，我们之前已经分析出来了状态转移方程，但是循环的顺序应该怎样呢？
for (int i = 0; i < nums.size(); ++i)
for (int j = 0; j <= 背包容量; ++j)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);for (int j = 0; j <= 背包容量; ++j)
for (int i = 0; i < nums.size(); ++i)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);先遍历 物品还是先遍历背包重量呢？
其实都可以！！但是先遍历物品更好理解。（因为需要的dp[i - 1][j], dp[i - 1][j - w]都在左上方向）
我们还是画图来理解下，数字代表遍历到的顺序
先遍历物品
————————————>背包容量
| 1 2 3 4 5 6
| 7 8 9 ....
|
|
v
物品先遍历背包重量
————————————>背包容量
| 1 6
| 2 7
| 3 8
| 4 9
v 5 ...
物品两种方式，左上的值都是更新过的因此都可
一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。
for (int i = 0; i < nums.size(); ++i)
for (int j = 背包容量; j >= w ; --j) // 防止越界j >= w
dp[j] = max(dp[j], dp[j - w] + v);很简单如果先遍历物品，走到7的时候左上的信息还在
————————————>背包容量
| 6 5 4 3 2 1
| ... 9 8 7
|
|
v
物品如果先遍历背包容量（错误）
那么这个顺序，我们可以清楚分析到一点，从1->5一开始就错了，因为6的信息还没有，但是2应该由1 和 6 以及 6同行的信息（左上）得到。
————————————>背包容量
| 6 1
| 7 2
| 8 3
| 9 4
| ... 5
|
v
完全背包，元素可重复使用
与0-1背包的区别主要是空间优化的时候正序就行
在完全背包中，不论空间是二维，还是优化为一维，两个for循环嵌套顺序同样无所谓！
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的（左上）。只要保证下标j之前的dp[j]都是经过计算的就可以了。
先遍历物品
————————————>背包容量
| 1 2 3 4 5 6
| 7 8 9 ....
|
|
v
物品先遍历背包重量
————————————>背包容量
| 1 6
| 2 7
| 3 8
| 4 9
v 5 ...
物品进入本题的讲解
上面讲解背包问题的时候注意，我们都是分析的最最最最最最最最典型的背包，想要装得最多，因此状态转移方程很固定。
但是面试题几乎没有纯背包问题（包括组合背包，分组背包等…），都是变式，但是也是有套路可寻的。
这道题的分支是：
填满背包的排列
填满背包
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[i]种方法
有哪些来源可以推出dp[j]呢？
举一个例子,已知dp[3]，填满背包容量为3的话，有dp[3]种方法。
那么只需要搞到一个2（nums[i]），有dp[3]方法可以凑齐容量为3的背包，相应的就有多少种方法可以凑齐容量为5的背包。
那么需要把这些方法累加起来就可以了，dp[i] += dp[j - nums[j]]
所以求组合类问题的公式，都是类似这种：
dp[j] += dp[j - nums[i]];dp数组如何初始化
dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品。
组合？排序？
我们先来看 外层for循环遍历物品，内层for遍历背包容量的情况。
代码如下：
for (int i = 0; i < nums.size(); i++) { // 遍历物品
for (int j = nums[i]; j <= amount; j++) { // 遍历背包容量
dp[j] += dp[j - nums[i]];
}
}假设：nums[0] = 1，nums[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数！
如果把两个for交换顺序，代码如下：
for (int j = 0; j <= amount; j++) { // 遍历背包容量
for (int i = 0; i < nums.size(); i++) { // 遍历物品
if (j - nums[i] >= 0) dp[j] += dp[j - nums[i]];
}
}背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数！
代码
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; ++i) // 遍历背包容量
for (const int& num : nums) { // 遍历物品
if (i < num || dp[i] > INT_MAX - dp[i - num]) continue; //cpp防止过程中溢出
dp[i] += dp[i - num];
}
return dp[target];
}
};组合问题举一反三
- 组合总和 Ⅳ（本题）
- 目标和
- 零钱兑换 II
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 1863 | 3182 | 58.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
