织梦做网站建立数据库网站关键词快速排名技术

377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

思路：

本题实质上是给一些数字，让他们在满足和是target的情况下随机排列组合，然后返回所有的排列数目。注意，本题和完全背包问题有所不同，完全背包问题不要求有先后顺序的区别，比如先放第i个物品再放第一个物品和先放第一个物品再放第二个物品没有区别，但是本题例如1+3=4和3+1=4就是不一样，因此dp数组的含义，具体做法有所不同。

dp[i]表示和是i的所有组合数目。dp[i]+=dp[i-nums[i]]。（对于可以视为在和是i-nums[i]的所有排列方法后面加一个nums[i]，注意我的说法，是在所有组合的后面，是后面而不是任意位置，这一点接下来会用到！）

对于循环，本题外层循环是i从0到target，内层循环是对nums数组的遍历。本题外层循环个人理解方式是规定目前最后进入的元素该是那个，然后内存循环表示要进nums[i]，这样就可以实现每次遍历都在对应的上一个外层循环排序后加一个元素，保证了没有重复。这里不太好说明，就比如假如有数字1，2，3，第一次会有三个式子1=1，2=2，3=3.然后第二次大循环会有1+1=2，1+2=3，1+3=4，2+1=3，2+2=4，2+3=5,3+1=4,3+2=5,3+3=6,可以很明显看出除了最后一个元素外的前面那一串式子就是上一次外层循环得到的所有式子。（即1，2，3）

初始化：

dp[0]=1，因为一个元素都没有才能使得和为0，只有一种组合。

注意：本题所有排列组合数目可能会非常大，因此通过模运算来保证不会超出int存储范围。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {const int mod=1e10;int n=nums.size();vector<long long>dp(target+1,0);dp[0]=1;for(int j=0;j<=target;j++){for(int i=0;i<n;i++){  if(j-nums[i]>=0)dp[j]+=dp[j-nums[i]];dp[j]%=mod;}}return dp[target];}
};