377. 组合总和 IV

发表于 2021-04-25 分类于算　　法阅读次数：本文字数： 1.7k 阅读时长 ≈ 6 分钟

这是今天的打卡题目，看标题，就知道这是系列题目，不过那不重要的。我们先来看看题目：

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素互不相同
1 <= target <= 1000
组合总和IV <– 传送门

乍一看是排列组合，我首先想到的就是回溯法，然后，又一细看，发现只需要求出数量，并没有说要求出所有组合，那就要警惕了，这题目肯定不适合用回溯法去穷举的。不过仔细看提示部分，觉得似乎数据规模又不大，只有区区 200 个数据。不过呢，咱们毛想想排列组合问题，一半都是阶乘的复杂度，那么 200! 已经很恐怖了。

其实，到这里，我们已经彻底堵死了穷举所有排列组合的可能了。只能静心去想想，到底怎么才能算出来这个数字了。先看看例子吧，nums = [1,2,3]，target = 4，这种情况下，有 7 种，可以看到，每个数字可以采用是多次的，然后，这里有一个关键的提醒是，“顺序不同的序列被视为不同组合”，其实，考虑到顺序问题，已经是排列问题了，不能叫组合问题，真正的组合是无序的。

这是一个至关重要的提示！其实，这时候，我脑子里想到的是，要去缩小问题的规模，无非怎么缩小的问题。还是用我惯用的伎俩，减 1 法。对于 target = 4 来说，我们来看看，4 - 1 = 3，和原问题有什么关联，因为数字可以重复用，那么 3 在 nums = [1,2,3] 上面的组合有几种呢？不难发现，有 4 种，然后是 target = 2，然后是 target = 1，于是，我们不难发现，对于 f(4) 来说，f(4) = f(3) + f(2) + f(1) = 7，太棒了！我们几乎已经知道递归算法了。

这里还有两个问题没解决，第一，f(4) 为什么这么分解？因为，nums 里有 3 个数字，f(3) ～f(1) ，正好是 target - nums[i] 的几个值，不是随便挑选的。物理意义也比较明确，就是从 target 里，减去一个数字，然后剩下数字的组合数之和，就是最终结果。第二个问题，f(3)～f(1) 怎么算，其实，只是递归去解每个子问题就行，那么边界是几呢？不难想到，边界是 f(0)，那么，f(0) 到底是几呢？这是个极其“平凡而不显然”的问题！

我们看看 f(1)，在 nums = [1,2,3] 上面，1 有几种组合呢？显然只有 1 种。按照递归解法，其实 f(1) = f(0)，然后我们就知道了一个事实，f(0) = 1，其实，这里很典型的就是， target 取值范围是 [1, 1000] ，但我们又在谈论 target = 0 的问题，我发现 LC 的很多题目，留了这种陷阱，如果，对于递归题，递推题，求解出 f(0) 往往是破题的关键。

所有难题解决了，然后我写出了递归解：

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        n = len(nums)

        def combine(s: int) -> int:
            if s == 0: 
                return 1
            
            res = 0
            for i in range(n):
                if s - nums[i] >= 0:
                    res += combine(s - nums[i])
            return res
        
        return combine(target

这个解法是非常直观和简洁的，我们把 f(target)，分解为若干子问题 f(target - nums[i])，然后对所有子问题的解，求和即可。然后通过自测，我们很容易发现，这个解法是正确的，但是，在 target = 30 的时候，报了超时，再往上，超出了答案的数量范围，我们不用考虑，但是 TLE，即是说明，正确答案能在多项式时间求出，而你的解法不行。显然时间复杂度不够优化。这也是意料之中的事情。

这个递归算法，每一重递归里，原问题被分解为 n 个子问题，n 是 nums 的长度，规模在 200，如果 nums 里有数字 1，那么最深的一个分支，可以深入 target 层，target 的规模是 1000，其实答案不能超过 2 的 32 次方，我们测试出来 target 规模不能超过 30 左右。那么类比与二叉树的结构，这个递归算法的复杂度大概是O( n ^ target)，最坏相当于是 200^30 那么大，绝对是天文数字了。

为什么呢？还是回到那个例子，f(4) = f(3) + f(2) + f(1)，而 f(3) = f(2) + f(1)，这就发现一个问题，递归过程种 f(2) 至少被计算两遍，而 f(1) 就计算次数更多了。自然而然想到的，第一，弄个缓存来记忆重复求解的。不过，显然这题是可以“动态规划”的。

重叠子问题，无后效性。而且，到这里，状态转移方程也呼之欲出了。

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

其实，这个动态规划的写法还是不显然的，尤其对我这种不熟练的来说，递归写法是很显然的，但是动态规划其实是把顺序颠倒一下，从而省略了所有重复计算。那么这个 for 到底怎么写就很关键。target - nums[i]，因为 nums 这个集合不是连续的，也不知道有几个数字，那么，顺序颠倒过来后，到底怎么才能找到这个离散遍历的序列呢？我抱着试一试的想法，何不把 target 以降所有的值都求出来呢？所以就写了如上算法，幸好，这个算法是对的。

其实，到这里，我们才能忐忑地去反向思考，这里隐含了很多小的点。比如 target 以降，很多的值其实不用求的，例如 nums = [5]，target = 9，这个例子，我们其实只要求 f(9)，而 f(9) = f(4)，可是“动态规划”算法里，显然会去求每一个值的。那些又有什么物理意义呢？

其实，这里我们发现了另一个边界值。就是如果 nums 里的数字不能把 target 减到 0，那么组合数是等于 0 的。细细品味一下这行 dp = [1] + [0] * target。也是非常“平凡但是不显然”的。

这个动态规划算法的时间复杂度，根据代码不难分析，O(n*target)。效率还是相当高的。