跳转至

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]