题目：
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.
一开始最直接的思路就是递归：拿给定的例子来说就是nums=[1,2,3] target=4 相当于，那么遍历nums,每次递归调用时将target-nums[i]作为参数传入下一层，这样就可以找到所有的组合，然后返回结果的个数即可。但是这样的尝试却TLE了，分析发现确实如此，即使nums中数目不多，只要target一大，那么递归的层数就会过多，这样一来极大的增加了时间复杂度。
随后便再想是不是能用DP来进行求解，从这个角度来看的话，这个问题就特别想斐波那契数列的DP求法，题目要求求得是不同排列的数目，那么很容易会发现，每一个数所得的排列数目都和之前的排列数目有关，和刚才的递归想法一致，只不过我们关注的是排列的数目而不是排列本身，target=4所得的排列数目按照[1,2,3]就可以分解为target=3，target=2，target=1的数目之和。如此一来，只要了解了nums就可以一步一步计算出target的排列数目。
java代码如下：
public int combinationSum4(int[] nums, int target) {
int result[]=new int[target+1];
result[0]=1;//如果target是nums中的一员，那么nums[0]就可以来表示这个数本身就可以当做一个排列
for (int i=1;i<target+1;i++)
for (int j=0;j<nums.length;j++){
if(i-nums[j]<0)
continue;
result[i]+=result[i-nums[j]];
}
return result[target];
}
python代码如下：
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
result=[0]*(target+1)
result[0]=1
for i in xrange(0,target+1):
for j in xrange(0,len(nums)):
if i-nums[j]<0:
continue
result[i]+=result[i-nums[j]]
return result[target]
最后附上TLE 递归方法：（java）
public class CombinationSumIV {
//递归复杂度太高，须其他方法
private static int count=0;
public int combinationSum4(int[] nums, int target) {
if (nums.length==0){
return 0;
}
ArrayList<Integer> temresult=new ArrayList<>();
for(int i:nums){
if (i > target){
continue;
}
else{
temresult.add(i);
deep(nums,target-i,temresult);
}
}
return count;
}
private void deep(int[] nums,int target,ArrayList<Integer> temresult){
if (target==0){
count++;
}
else {
for (int i:nums){
if (i>target){
continue;
}
else{
temresult.add(i);
deep(nums,target-i,temresult);
}
}
}
}
}