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 = 4The 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())。

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

1 class Solution { 2 public: 3     int combinationSum4(vector
     
      & nums, int target) { 4         if(target<=0){ 5             return !target; 6         } 7         int i,n=nums.size(),res=0; 8         for(i=0;i
     

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

 

 

代码：

自底向上：

1 class Solution { 2 public: 3     int combinationSum4(vector
     
      & nums, int target) { 4         //局部域参数申请，未初始化时，可能不为0 5         //例如 6         //int *values=new int[target]; 7         //此时values数组的每个数的取值为任意值！ 8         vector
      
        values(target+1); 9         values[0]=1;10         for(int i=1;i<=target;i++){11             for(int j=0;j
       
        =0){14                     values[i]=values[i]+values[temp];15                 }16             }17         }18         return values[target];19     }20 };
       
      
     

 

 

自顶向下：

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

1 class Solution { 2 public: 3     int combinationSum4(vector
     
       nums,vector
      
       & values,int target) { 4         if(target<=0){ 5             return !target; 6         } 7         if(values[target]==-1){ 8             values[target]=0; 9             for(int i=0;i
       

& nums, int target) {16 //values初始化为0不合适，因为values[i]==0可以意味着i不能被所给数组成，此时i已经被遍历过17 //也可以意味着i没有被遍历18 //所以设置values的初始值为0，还是不能避免大量重复的遍历操作19 vector

values(target+1,-1);20 return combinationSum4(nums,values,target);21 }22 };