## Dynamic Programming - 377. Combination Sum IV

Updated on with 0 views and 0 comments

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.
``````

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]
}
``````