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())。
注意冗余的存在，例如下面的代码就没有去除冗余：
1 class Solution { 2 public: 3 int combinationSum4(vector<int>& nums, int target) { 4 if(target<=0){ 5 return !target; 6 } 7 int i,n=nums.size(),res=0; 8 for(i=0;i<n;i++){ 9 res+=combinationSum4(nums,target-nums[i]); 10 } 11 return res; 12 } 13 };
所以可以先申请内存，记录已经计算过的数的情况。
代码：
自底向上：
1 class Solution { 2 public: 3 int combinationSum4(vector<int>& nums, int target) { 4 //局部域参数申请，未初始化时，可能不为0 5 //例如 6 //int *values=new int[target]; 7 //此时values数组的每个数的取值为任意值！ 8 vector<int> values(target+1); 9 values[0]=1; 10 for(int i=1;i<=target;i++){ 11 for(int j=0;j<nums.size();j++){ 12 int temp=i-nums[j]; 13 if(temp>=0){ 14 values[i]=values[i]+values[temp]; 15 } 16 } 17 } 18 return values[target]; 19 } 20 };
自顶向下：
https://leetcode.com/problems/distinct-subsequences/
Leetcode 377. Combination Sum IV
原文：http://www.cnblogs.com/Deribs4/p/5719474.html