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?

题目含义：给定多个正整数且没有重复，从中挑选任意个数字（可以重复）使其加起来等于给定目标值target

思路：

 dp[i]表示总和为i的情况数，假设当前整数值等于n(n<i)，如果我们知道了 dp[i-n] 的情况数，因为 dp[i-n] 的每一种情况加n都等于dp[i]，所以说dp[i-n]和dp[i]的情况数相同。

 每获取一个整数n，都会给了dp[i]添加dp[i-n]种情况，所以公式为dp[i] = dp[i] + dp[i-n]

例如：

 当前元素n等于1时，dp[9] = dp[9] + dp[9-1]

　　　　　　　　　 dp[8] = dp[8] + dp[8-1]

　　　　　　　　　　 ...

　　　　　　　　　 dp[1] = dp[1] + dp[1-1]

 当前元素n等于2时，dp[9] = dp[9] + dp[9-2]

　　　　　　　　     dp[8] = dp[8] + dp[8-2]

　　　　　　　　　　 ...

　　　　　　　　     dp[2] = dp[2] + dp[2-2]

 当前元素n等于3时，dp[9] = dp[9] + dp[9-3]

　　　　　　　　     dp[8] = dp[8] + dp[8-3]

　　　　　　　　　　 ...

　　　　　　　　     dp[3] = dp[3] + dp[3-3]

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

 

 类似题目： 

请注意：本题目选取的数字可以多次重复，而题目494中的数字不可重复选择