Daily LeetCode 377. Combination Sum IV

https://leetcode.com/problems/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?

思路及代码：

给定一个nums数组和target，我们从nums中选数，找出所有组合，使得组合的和为target，最后返回组合个数。需要注意的是，不同排列顺序的组合被看作是不同的组合，需要重复计数。

我们可以反着思考这个问题，假设我们只需要再找一个数就能够使得和为target，我们从nums数组中找任何一个小于target的数即可。维护一维数组dp，dp[i]表示当target为i时，能够找到的组合数，dp[target] = sum(dp[target - nums[i]]), 0 <= i < len(nums), target >= nums[i]。由于0只能够由0得到，因此dp[0]=1。在题目中给的例子中，dp[4] = dp[3] + dp[2] + dp[1]。

代码：

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):
            for j in range(len(nums)):
                if i >= nums[j]:
                    dp[i] += dp[i - nums[j]]

        return dp[target]        

给定数组中存在负数的情况：

当给定数组中存在负数时，组合数将是无穷无尽的。

例如，给定[1, -1, 2, -2]，target为0时，我们能够找出无穷多个组合，来满足和为0这一条件。