Leetcode 377. Combination Sum IV

377. Combination Sum IV

• Total Accepted: 2547
• Total Submissions: 6581
• Difficulty: Medium

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

思路：DP，可以自顶向下，也可以自底向上。

假设values[i]表示的是i的被组合情况，显然有values[i]=values[i-nums[0]]+...+values[i-nums[n-1]](n=nums.size())。

注意冗余遍历的存在，例如下面的代码就没有去除冗余的遍历：

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        if(target<=0){
            return !target;
        }
        int i,n=nums.size(),res=0;
        for(i=0;i<n;i++){
            res+=combinationSum4(nums,target-nums[i]);
        }
        return res;
    }
};

所以可以先申请内存，记录已经计算过的数的情况。

代码：

自底向上：

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        //局部域参数申请，未初始化时，可能不为0
        //例如
        //int *values=new int[target];
        //此时values数组的每个数的取值为任意值！
        vector<int> values(target+1);
        values[0]=1;
        for(int i=1;i<=target;i++){
            for(int j=0;j<nums.size();j++){
                int temp=i-nums[j];
                if(temp>=0){
                    values[i]=values[i]+values[temp];
                }
            }
        }
        return values[target];
    }
};

自顶向下：

values初始化为0不合适，因为values[i]==0可以意味着i不能被所给数组成，此时i已经被遍历过；也可以意味着i没有被遍历。所以设置values的初始值为0，还是不能避免大量重复的遍历操作。

class Solution {
public:
    int combinationSum4(vector<int> nums,vector<int>& values,int target) {
        if(target<=0){
            return !target;
        }
        if(values[target]==-1){
            values[target]=0;
            for(int i=0;i<nums.size();i++){
                values[target]+=combinationSum4(nums,values,target-nums[i]);
            }
        }
        return values[target];
    }
    int combinationSum4(vector<int>& nums, int target) {
        //values初始化为0不合适，因为values[i]==0可以意味着i不能被所给数组成，此时i已经被遍历过
        //也可以意味着i没有被遍历
        //所以设置values的初始值为0，还是不能避免大量重复的遍历操作
        vector<int> values(target+1,-1);
        return combinationSum4(nums,values,target);
    }
};