【DP】377. Combination Sum IV

问题描述：

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?

解题思路：

方法1：BFS（超时 TLE）

第一种想法是使用 【DP、BFS】322. Coin Change 这道题中的 BFS 方法，只不过这时 BFS 的目标是求能到达 amount 的次数，并且不使用 visited 剪枝。因此，很快拍出下面代码：

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dis = [(0, 0)]
        layer = 0
        ans = 0
        while len(dis) > 0:
            while len(dis) > 0 and dis[0][1] == layer:
                tem = dis.pop(0)
                if tem[0] == target:
                    ans += 1
                for num in nums:
                    if tem[0] + num <= target:
                        dis.append((tem[0]+num, layer+1))
            layer += 1
        return ans

但是这种情况下，超时了。假设硬币中有 1，amount 又很大，构造这棵树的时间复杂度最坏可能达到 O(2^(amount))，这是不可接受的，因此这种想法不行。

方法2：DP（接受 AC）

如果使用动态规划的思想，就和 Leetcode 【DP】518. Coin Change 2 的解法很类似了，只不过这道题是求排列数，找硬币的题是求组合数。

在找硬币问题中分析了，由于是求组合数，所以外层循环应该是对 coins 的循环。但是这道题是是求排列数，nums 里面的数可以不同顺序的出现，因此这道题的内层循环应该是 nums，外层循环应该是不同的目标 i。

因此，类似于 【DP】518. Coin Change 2 ，可以想到如下算法：

• 创建一个 dp[1+target] 数组，其中 dp[i] 表示目标为 i 时的排列方案数；
• 初始化 dp[0] = 1，表示目标为 0 的时候方案数为 1，其他位置 dp[i] 为 0；
• 外层循环是对不同目标 i 的循环，内层循环是对 nums 的循环；可以想到转移方程：dp[i] = ∑ dp[i-nums[j]]，表示：目标为 i 时的方案数 = 目标为 i-nums[j] 的方案数的加和。∑ 次数等于内层循环次数。
• 最后，dp[-1] 就是答案。

Python3 实现：

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

print(Solution().combinationSum4([2,1], 3))  # 3 (111、12、21)