组合总和 Ⅳ

难度: Medium

给定一个由不同正整数组成的数组 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

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

注意：本题与主站 377 题相同：https://leetcode-cn.com/problems/combination-sum-iv/

Submission

运行时间: 22 ms

内存: 16.3 MB

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        n_set = set(nums)

        @cache
        def comb(target: int) -> int:
            if target == 0: return 1
            ans = 0
            for num in nums:
                if num > target: return ans
                ans += comb(target-num)
            return ans
        
        return comb(target)

Explain

此题解使用了动态规划（DP）的思想来解决问题。首先，题解对输入数组进行了排序，这样做可以优化后续的处理，因为一旦遍历到的数大于当前目标值，就可以停止循环，避免无用的计算。接着，题解利用递归函数 'comb' 来计算可以达到特定目标值的组合数。每当 'comb' 被调用时，如果目标值为0，意味着找到了一种有效的组合，因此返回1。否则，函数会遍历数组中的每个数，递归地调用 'comb' 函数以当前数值减去数组中的数作为新的目标，这样逐渐减小目标值，直到目标为0或无法进一步分解。此外，使用 '@cache' 装饰器来存储已计算的结果，避免重复计算，提高效率。

时间复杂度: O(n*target)

空间复杂度: O(target)

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()  # 对数组进行排序，有助于后续优化
        n_set = set(nums)  # 转换为集合，虽在此代码中未用到

        @cache  # 使用缓存装饰器，避免重复计算
        def comb(target: int) -> int:
            if target == 0: return 1  # 当目标为0时，说明找到一种组合，返回1
            ans = 0
            for num in nums:  # 遍历每个数字
                if num > target: return ans  # 如果数字大于目标，停止遍历
                ans += comb(target - num)  # 递归计算剩余目标的组合数
            return ans  # 返回计算结果
        
        return comb(target)  # 计算并返回目标值的组合数

Explore

在题解中，数组排序的主要优化在于提高遍历效率和减少无用计算。排序后，当在递归函数中遍历到一个数字大于当前目标值（target）时，可以立即停止遍历。因为后续的数都会更大，继续遍历这些数只会得到不满足条件的组合或重复计算。这样，排序帮助减少了对不可能产生有效结果的数的无效调用，从而节省了时间和计算资源。

在递归函数中，当遇到一个数`num`大于目标值`target`时，可以直接返回当前的答案，因为数组已经排序，所有后续的数都将大于或等于`num`。这意味着，如果`num`已经超过了`target`，那么所有接下来的数无论如何组合，都不可能使得总和恰好等于`target`。因此，继续遍历这些数只会导致不必要的计算，没有必要继续检查更大的数。这是一种剪枝操作，可以有效减少计算量和提高效率。

在这个动态规划的问题中，初始边界条件是当目标值`target`为0时，函数应返回1。这是因为如果目标值为0，表示不需要任何数字就已经满足了目标条件（即总和为0的唯一组合是不选任何数字），这构成了一个有效的组合。这个初始条件是递归和动态规划的基础，为递归提供了一个明确的终止条件和起点。从这个基础出发，函数可以通过递归调用来构建解决更大`target`值的解决方案。