给定一个正整数数组，找出所有可以相加得到目标正整数的组合

Example:

给定数组:{1,2,3}
目标数:4
可能情况:
    {1,1,1,1}
    {1,1,2},{1,2,1},{2,1,1}
    {2,2}
    {1,3},{3,1}
组合数:7

解题思路

设目标数 i 的组合数为 dp[i] ，可知 dp[i] += dp[i] + dp[i-num] ，例如本题计算 dp[3] 时，数组为 {1,2,3} ，因 3 可拆分为 1+x ，此时 x 则为 dp[2] ，也可拆为 2+x ，此时 x 则为 dp[1] ，因此， dp[i]=dp[i-nums[0]] + dp[i-nums[1]] + dp[i-nums[2]].......dp[i-nums[nums.length-1]] 。

代码

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 1 ; i <= target ; i ++){
            for(int num:nums){
                if(i >= num) dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }
}