Dynamic Programming - 377. Combination Sum IV

377. Combination Sum IV

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?

Credits:
Special thanks to [@pbrother](https://leetcode.com/pbrother/) for adding this problem and creating all test cases.

思路：

这一个组合的题目与其他三题最大的不同在于，这个组合可以重复还和顺序有关，用回溯做，有一个问题在于回溯条件难写，这里使用动态规划来做，把问题拆解为对于数组中的某一个数，用数组中的数和这个数能组成的种数，比如求target = 10，就得知道target等于target-nums[i], (i in [0, len(nums) -1)的时候，有多少种组合。

代码：

go：

/*func combinationSum4(nums []int, target int) int {
    dp := make([]int, target + 1)
    for i := range dp{
        dp[i] = -1
    }
   
    return combination(&dp, nums, 0, target)
}


func combination(dp *[]int, nums[]int, sum int, target int) int {
    if target < sum {
        return 0
    }
    
    // base case
    if target == sum {
        return 1
    }
    
    if (*dp)[sum] != -1 {
        return (*dp)[sum]
    }
    
    
    var ans int
    for i := range nums {
        ans += combination(dp, nums, sum + nums[i], target)
    }
    (*dp)[sum] = ans;
    
    return ans
}*/

func combinationSum4(nums []int, target int) int {
    dp := make([]int, target + 1)
    dp[0] = 1
    for i := 1; i <= target; i++ {
        for _, num := range nums {
            if i - num >= 0 {
                dp[i] += dp[i - num]
            }
        }
    }
    
    return dp[target]
}