Skip to content

377 combination sum iv

377. Combination Sum IV

题目:

https://leetcode.com/problems/combination-sum-iv/

难度:

Medium

直接用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)

说起来标签是dp,也知道是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的所有情况了

AC代码

class Solution(object):
    def combinationSum4(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        dp = [0 for i in range(target+1)]

        dp[0] = 1

        for i in range(target+1):
            for candidate in candidates:
                if i >= candidate:
                    dp[i] += dp[i - candidate]
        return dp[-1]


回到顶部