Skip to content

Latest commit

 

History

History
164 lines (105 loc) · 3.47 KB

0377._combination_sum_iv.md

File metadata and controls

164 lines (105 loc) · 3.47 KB

377. Combination Sum IV

难度: Medium

刷题内容

原题连接

内容描述

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 for adding this problem and creating all test cases.

解题方案

思路 1 - 时间复杂度: O(2^n)- 空间复杂度: O(2^n)******

直接用combination sum的思路： 超时

class Solution(object):
    def combinationSum4(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def combSum(candidates, target, start, valueList):
            length = len(candidates)
            if target == 0 :
                res.append(valueList)
            for i in range(start, length):
                if target < candidates[i]:
                    return 
                combSum(candidates, target - candidates[i], 0, valueList + [candidates[i]])

        candidates = list(set(candidates))
        candidates.sort()
        res = []
        combSum(candidates, target, 0, [])
        return len(res)

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

dp,状态转移方程：

参考:

http://www.cnblogs.com/grandyang/p/5705750.html

我们需要一个一维数组dp，其中dp[i]表示目标数为i的解的个数，然后我们从1遍历到target，对于每一个数i，遍历nums数组，如果i>=x, dp[i] += dp[i - x]。这个也很好理解，比如说对于[1,2,3] 4，这个例子，当我们在计算dp[3]的时候，3可以拆分为1+x，而x即为dp[2]，3也可以拆分为2+x，此时x为dp[1]，3同样可以拆为3+x，此时x为dp[0]，我们把所有的情况加起来就是组成3的所有情况了

要注意dp数组使用条件：

  1. 前推数组不能太长
  2. 需要找出连续的递推方程

beats 96.77%

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [0] * (target+1)
        dp[0] = 1
        for j in range(target+1):
            for num in nums:
                if j >= num:
                    dp[j] += dp[j-num]
        return dp[target]

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(N)******

记忆化搜索

beats 38.31%

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """  
        cache = {0:1}
        def helper(remain):
            if remain < 0:
                return 0
            if remain in cache:
                return cache[remain]
            res = 0
            for i in range(len(nums)):
                res += helper(remain-nums[i])
            cache[remain] = res
            return res
        
        return helper(target)