跳转至

LeetCode: 377. 组合总和 Ⅳ

1、题目描述

​

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

进阶： 如果给定的数组中含有负数会怎么样？ 问题会产生什么变化？ 我们需要在题目中添加什么限制来允许负数的出现？

致谢： 特别感谢 @pbrother 添加此问题并创建所有测试用例。

2、解题思路

​ 这道题使用动态规划来做

  • 首先，将书数组中的所有的数字，建立哈希，方便查找

  • 然后，建立dp[target+1]

  • 然后对每一个下标开始判断

  • 例如，对和为5进行判断

  • dp[5] = dp[0]+5(if 5 in nums) + dp[1]+4(if 4 in nums) + dp[2]+3(if 3 in nums) + dp[3]+2(if 2 in nums) + dp[4]+1(if 1 in nums)

  • 以此类推，最后得到结果

​ 上面的思路好像有点问题，还超时了

​ 换个思路，再来一次，这一次我们使用构造法，

首先，将dp数组创建出来，然后将所有的nums数组中出现的数字对应的下标置一

接着，从前面向后进行扫描，遇到不为0的数，就用这个数字，加上nums中的数字，将对应的下标的数字增加1

举个例子

nums = [1, 2, 3]
target = 4
首先，创建dp
[0 0 0 0 0]
然后初始化
[0 1 1 1 0]
然后开始扫描，找到第一个不为0的数，也就是下标为1的那个1
然后判断 加上对应的nums的数字，是不是小于等于target
1+1
1+2
1+3
如果小于，对应的要加1
得到新的dp
[0 1 2 2 1]
然后继续判断，到最后位置

class Solution:
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [0] * (target + 1)

        for i in nums:
            if i <= target:
                dp[i] = 1

        for i in range(target + 1):
            if dp[i] == 0:
                continue

            for j in nums:
                if i + j <= target:
                    dp[i + j] += dp[i]
        return dp[-1]