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

思路

这个题如果还是照着combination sum的思路来做的话很容易超时, 可行的解法是DP bottom up的方式来求解. 参考Youtube

Swift 解法

func combinationSum4(_ nums: [Int], _ target: Int) -> Int {  
        var dp = Array(repeating: 0.0, count: target + 1)
        dp[0] = 1

        for i in 1...target {
            for num in nums {
                if i - num >= 0 {
                    dp[i] += dp[i - num]
                }
            }
        }

        return Int(dp[target])
    }

至于上面为什么为什么用了double 和Int 的转换,是因为有些test case特别special导致会overflow的问题。

chenbo

编程爱好者

Singapore