377. 组合总和 Ⅳ

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

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

动态规划-可重复+排列（需要考虑选取元素的顺序）+数组递推+滚动更新+贪心。背包问题，先遍历容量，再遍历物品。

dp[i] 表示选取的元素之和等于 i 的组合个数，边界是 dp[0]=1。只有当不选取任何元素时，元素之和才为 0， 因此只有 1 种方案。遍历 $i$ 从 1 到 target，对于每个 $i$， 进行如下操作：遍历数组 nums 中的每个元素 $num$ ，当 $num \leq i$ 时，将 $dp[i-num]$ 的值加到 $dp[i]$。 最终得到 $dp[target]$ 的值即为答案。 for循环反过来就是518. 零钱兑换II https://leetcode.cn/problems/coin-change-ii/description/ 这题本质上是 70. 爬楼梯，每次从 nums 中选一个数， 作为往上爬的台阶数，问爬 target 个台阶有多少种方案。70 那题可以看作 nums=[1,2]。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 初始化 dp 数组，dp[i] 表示凑成目标数 i 的组合个数。i=0和i>0时计算逻辑不一样，所以多申请一位以统一这两部分的逻辑
        int[] dp = new int[target + 1];
        dp[0] = 1; // 凑成目标数 0 的组合只有一种，即空组合

        // 遍历从 1 到 target 的所有目标数。即先遍历容量，再遍历物品。
        // 重点。两个for循环的顺序不能换！因为dp[i]依赖于dp[i-num]。并且题目要求可以重复选择数字，即对每个dp[i]，都可以从头选择nums。
        // 或者这么理解：先遍历物品就相当于把物品的顺序确定了，即按照nums的顺序选择，但是题目说不同的顺序算不同的组合。
        for (int i = 1; i <= target; i++) {
            // 遍历所有的数字
            for (int num : nums) {
                // 如果当前数字小于等于当前目标数 i，则选择它
                if (num <= i) {
                    // 注意。更新 dp[i]，增加 dp[i - num] 的值，这里是在dp[i]的基础上累加，不是1+dp[i-m]，
                    // 因为我们要求的是所有的组合数。为什么不是+=dp[i-m]+1？其中1指选择当前num，
                    // 其实只要选择了dp[i-num]的组合，就自动选择了num这个数。
                    // 将 dp[i - num] 的所有组合数累加到 dp[i]，因为每一种组合都可以通过加上 num 形成新的组合。重点。
                    dp[i] += dp[i - num];
                }
            }
        }

        // 返回凑成目标数 target 的组合个数
        return dp[target];
    }
}

• 时间复杂度： $O(target\times n)$ ，其中 target 是目标值， $n$ 是数组 nums 的长度。需要计算长度为 target +1 的数组 $d p$ 的每个元素的值，对于每个元素，需要遍历数组 nums 之后计算元素值。
• 空间复杂度： $O(target)$ 。需要创建长度为 target +1 的数组 $d p$ 。

进阶问题

如果给定的数组中含有负数，则会导致出现无限长度的排列。

例如，假设数组 nums 中含有正整数 $a$ 和负整数 $-b$ (其中 $a>0, b>0,-b<0$ )， 则有 $a \times b+$ $(-b) \times a=0$ ，对于任意一个元素之和等于 target 的排列， 在该排列的后面添加 $b$ 个 $a$ 和 $a$ 个 $-b$之后，得到的新排列的元素之和仍然等于 target， 而且还可以在新排列的后面继续 $b$ 个 $a$ 和 $a$ 个 $-b$ 。因此只要存在元素之和等于 target 的排列，就能构造出无限长度的排列。

如果允许负数出现，则必须限制排列的最大长度，避免出现无限长度的排列，才能计算排列数。

动态规划-递归+备忘录

初始化为-1 表示没有计算过，结束条件i=0，查备忘录，枚举所有数，如果可选，则递归计算。计入备忘录。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 创建一个数组 memo，用于存储子问题的结果，以避免重复计算
        int[] memo = new int[target + 1];
        Arrays.fill(memo, -1); // 初始化 memo 数组，-1 表示这些值还没有被计算过
        
        // 调用递归函数 dfs，开始计算达到 target 的组合数
        return dfs(target, nums, memo);
    }

    private int dfs(int i, int[] nums, int[] memo) {
        // 基础情况：如果目标值 i 为 0，说明找到了一个组合，返回 1
        if (i == 0) { 
            return 1;
        }
        // 如果 memo[i] 不为 -1，说明这个子问题已经计算过，直接返回缓存的结果
        if (memo[i] != -1) { 
            return memo[i];
        }
        
        int res = 0; // 初始化组合数为 0
        // 遍历所有的可选数字。重点。
        for (int x : nums) {
            if (x <= i) { // 只有当当前数字 x 小于等于目标值 i 时，才有必要递归计算
                // 递归计算从 i-x 到 0 的组合数，并累加到结果中
                res += dfs(i - x, nums, memo);
            }
        }
        
        // 将计算结果存储到 memo[i] 中，记忆化结果，避免重复计算
        return memo[i] = res; 
    }
}

时空复杂度同上。

在没有记忆化的情况下，时间复杂度是指数级的，即 $O(n^\text{target})$