leetcode 377. Combination Sum IV

这道题也是完全背包问题。这道题和第518题几乎一摸一样，所不同的是，第518题要求的是组合数，而第377题要求的是排列数。虽然本题题目描述中说求的是组合数，但从例子1中（1，1，2）和（2，1，1）被当作两个不同的组法可以看出实际上求的是排列数。求排列数，外层循环必须是对背包容量进行遍历，内层循环必须是对物品遍历。

和第518题一样，存在中间结果整数溢出的问题，需特别处理。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {int n = nums.size();//dp[j]表示从nums中选若干个数使得总和等于j的选法数，相同的数字顺序不同代表不同的选法//dp数据类型使用double可以避免中间结果整数溢出无法通过部分测试用例的情况vector<double> dp(target+1,0);//除dp[0]外都初始化为0，表示从0个数中没有办法选到若干个数使得所选数的总和大于0。dp[0] = 1;//初始情况下，从0个数，选0个数，使得所选数的总和等于0，有1种选法，那就是不选，不选也是一种选法。for(int j = 0;j <= target;j++){for(int i = 0;i < n;i++){if(j>= nums[i])dp[j] = dp[j] + dp[j-nums[i]];}}return dp[target];}
};

严谨的做法

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {int n = nums.size();//valid[j]表示能否选若干个数使得所选数的总和等于jvector<bool> valid(target+1,false);valid[0] = true;for(int j = 0;j <= target;j++){for(int i = 0;i < n;i++){if(j >= nums[i])valid[j] = valid[j] || valid[j - nums[i]];}}if(!valid[target]) return 0;//dp[j]表示从nums中选若干个数使得总和等于j的选法数，相同的数字顺序不同代表不同的选法//dp数据类型使用double可以避免中间结果整数溢出无法通过部分测试用例的情况vector<double> dp(target+1,0);//除dp[0]外都初始化为0，表示从0个数中没有办法选到若干个数使得所选数的总和大于0。dp[0] = 1;//初始情况下，从0个数，选0个数，使得所选数的总和等于0，有1种选法，那就是不选，不选也是一种选法。for(int j = 0;j <= target;j++){for(int i = 0;i < n;i++){if(j>= nums[i])dp[j] = dp[j] + dp[j-nums[i]];}}return dp[target];}
};