这个题的思路是动态规划，DP[n]代表能组成n的组合数。算1-n就可以，因为都是正数。
算dp[n]的时候遍历num[1] to num[n] index = i
如果i < dp[n] 那么dp[n] = dp[n] + dp[n-i]
从逻辑上来考虑比较复杂，比如4=0+4 1+3 2+2 3+1 4+0
0+4 1 （1+1+1+1）
1+3 1的组合3的组合 2+2 2的组合2的组合 3+1 3的组合*1的组合 4+0 1 （4）1+4+4+4+1 然后除以2 因为重复了一遍
但是结果似乎不对看答案 算法是
dp[n] = dp[n] + dp[n-i]
比如4 从1遍历到4 1<4 dp[4] = dp[4] + dp[4-1]public int combinationSum4(int[] nums, int target) { int[] dp = new int[target+1]; dp[0] = 1; for(int n = 1; n < target+1;n++) { for(int m = 0; m < nums.length;m++) { if(n >= nums[m]) dp[n] = dp[n] + dp[n-nums[m]]; } } return dp[target]; } 代码很简单，但是发现这种逻辑很难，比如我就觉得无从下手。。
感觉DP的题重点是找到动态规划的递推式，已经习惯于DP[N]从dp[n-1]来找
这个题就不是。。
递推式dp[n] = dp[n] + dp[n-i]二刷：
一开始先排序，然后因为1，3和3,1这种都算有效，所以滑动窗口之类的没有意义。
而且，还有错，不能有效break。看一刷的答案，发现是动态规划。
当时不理解，现在理解了。
public int combinationSum4(int[] nums, int target) { Arrays.sort(nums); int[] dp = new int[target+1]; dp[0] = 1; for(int i = 1; i <=target;i++) { for(int j = 0; j < nums.length; j++) { if(i - nums[j]>=0) dp[i] = dp[i] + dp[i - nums[j]]; else break; } } return dp[target]; } 然后改进了一下，先排序，可以有效break，比直接遍历快一点点，而且好理解。
理解容易，不一定能想出来。
一开始有那个点意思，想到的是方法是递归。比如(nums[],target = 4 递归就变成(nums[],target-nums[n]) 仔细想想应该就是动态规划的思路，然后通过DP来减少重复计算。DP的双For loop大概可以总结为 i = 1 ~ n; j = 0 ~ i,从左边开始的话。
右边开始是 i = n~0; j = n~n-i???
------
三刷。
照着刚才的惯性DFS结果TLE了，做的时候就觉得不对……
应该是DP。。
dp[i]代表:
和是i的组合有多少种 的dp[4] = 1 + dp[3]4 = 1 + 3
4 = 2 + 2 4 = 3 + 1A + B的时候前面的A是nums里的数， 后者是可以组成B的左右组合，不能是dp[1] + dp[3]这样的话就重复计算了.
dp[1] + dp[2] 和 dp[2] + dp[1]计算了2次1+1+1...，这就是为啥一刷的办法不对。Time: O(nk)
Space: O(k)public class Solution { public int combinationSum4(int[] nums, int target) { if (nums.length == 0) return 0; Arrays.sort(nums); int[] dp = new int[target+1]; dp[0] = 1; for (int i = 1; i <= target; i++) { for (int j = 0; j < nums.length; j++) { if (i - nums[j] >= 0) dp[i] += dp[i - nums[j]]; else break; } } return dp[target]; }}