3. 组合总和Ⅳ（LeetCode-377）
题目
给你一个由 不同 整数组成的数组 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 <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000
**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
思路
由示例一最后一行得，题目看似求的组合数，实际上求的是排序数
五部曲
dp[j] 含义
凑成目标正整数为 j jj 的排列个数（使背包容量为 j jj 的背包恰好装满的组合数——不同排序算做不同组合）
递推公式
d p [ j ] + = d p [ j − d p [ n u m s ] ]
数组初始化
dp[0]=1
遍历顺序
先遍历背包，嵌套遍历物品，且物品遍历要正序
如果把遍历 nums（物品）放在外循环，遍历target的作为内循环的话，举⼀个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有 {3,1} 这样的集合，因为nums遍历放在外层，3只能出现在1后面
代码展示
class Solution { public: int combinationSum4(vector<int> &nums, int target) { vector<int> dp(target + 1); dp[0] = 1; for (int j = 0; j <= target; j++) { for (int i = 0; i < nums.size(); i++) { if (j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]) { dp[j] += dp[j - nums[i]]; } } } return dp[target]; } };
