文章 224
评论 6
浏览 200762
Dynamic Programming - 377. Combination Sum IV

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

标题:Dynamic Programming - 377. Combination Sum IV
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/09/04/1567530648306.html

Nothing just happens, it's all part of a plan.

取消