377. Combination Sum IV

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.

统计个数，如果还是用上3题的方法，超时了。

 1 class Solution {
 2 public:
 3     int finalres ;
 4     int combinationSum4(vector<int>& candidates, int target) {
 5         help(0,candidates,target);
 6         return finalres;
 7         
 8     }
 9     void help(int cursum,vector<int>& candidates,int target){
10         if(cursum==target)
11              finalres ++;
12         if(cursum>target)
13             return;
14         for(int i = 0;i<candidates.size();i++){
15             help(cursum,candidates,target-candidates[i]);
16         }
17     }
18 };

只是统计个数的话，其实是不用把每个组合都排出来，而且这个题并不是真正意义的排列问题

因为每个数字可以用无限次。

c++ leetcode有bug 所以用java

 1 class Solution {
 2    public int combinationSum4(int[] nums, int target) {
 3     int[] dp = new int[target + 1];
 4     dp[0] = 1;
 5     for (int i = 1; i <=target; i++) 
 6         for (int j = 0; j < nums.length; j++) 
 7             if (i - nums[j] >= 0) 
 8                 dp[i] += dp[i - nums[j]];   
 9     return dp[target];
10     }
11 }