LeetCode377. 组合总和 Ⅳ

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)
请注意，顺序不同的序列被视作不同的组合。
1
2
3
4
5
6
7
8
9
10
11
12

示例 2：

输入：nums = [9], target = 3
输出：0
1
2

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

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

二、题解

这道题要求我们找出由给定数组 nums 中的不同元素组成的总和等于 target 的组合个数，说是组合，其实实质上是排列，我在这篇文章里讲述了关于排列组合的区别并且手写了动态规划过程：https://blog.csdn.net/m0_61843614/article/details/132745696。

方法一：完全背包一维数组

动态规划思路

定义一个一维数组 dp，其中 dp[i] 表示总和为 i 的组合个数。

我们的目标是计算 dp[target]，也就是总和为 target 的组合个数。为了计算 dp[target]，可以考虑如下的思路：

1. 初始化一个长度为 target + 1 的数组 dp，并将其所有元素初始化为0。dp[i] 表示总和为 i 的组合个数。

2. 由于组合的元素可以重复使用，我们可以遍历数组 nums 中的每个元素，并尝试将其加入到总和为 i 的组合中。

3. 对于每个元素 nums[j]，我们可以检查 dp[i - nums[j]]，它表示总和为 i - nums[j] 的组合个数。我们可以将 dp[i - nums[j]] 加到 dp[i] 上，表示将 nums[j] 加入到当前组合中。

4. 重复上述步骤，直到遍历完数组 nums 中的所有元素。

5. 最终，dp[target] 就是我们要求的答案，表示总和为 target 的组合个数。

代码分析

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<long long> dp(target + 1, 0);
        dp[0] = 1;  // 初始化，总和为0的组合个数为1
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (nums[j] <= i && dp[i] < INT_MAX - dp[i - nums[j]]) {
                    dp[i] = dp[i] + dp[i - nums[j]];  // 更新 dp[i]
                }
            }
        }
        return dp[target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

代码解释：

• 我们定义了一个一维数组 dp，长度为 target + 1，并将所有元素初始化为0。

• 初始化 dp[0] 为1，因为总和为0的组合只有一种方式，就是什么都不选。

• 使用两个嵌套的循环，外层循环遍历所有可能的总和 i，内层循环遍历数组 nums 中的所有元素。

• 在内层循环中，我们检查当前元素 nums[j] 是否小于等于 i，如果是，就说明可以将 nums[j] 加入到总和为 i 的组合中。

• 如果 dp[i] 的值还没有越界（小于 INT_MAX - dp[i - nums[j]]），则将 dp[i - nums[j]] 的值加到 dp[i] 上，表示将 nums[j] 加入到当前组合中。

• 最终，返回 dp[target]，即总和为 target 的组合个数。

方法二：动态规划二维数组

先给出代码：

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        //dp[j][i]意义是背包容量为i的情况下，最后一个加入的数字是从nums[0]到nums[i]之间的方法的总数
        vector<vector<long long>> dp(nums.size(), vector<long long>(target + 1, 0));
        dp[0][0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (j > 0) {
                    dp[j][i] = dp[j - 1][i];
                }
                if (i >= nums[j] && dp[j][i] < INT_MAX - dp[nums.size() - 1][i - nums[j]]) {
                    dp[j][i] += dp[nums.size() - 1][i - nums[j]];
                }
            }
        }
        return dp[nums.size() - 1][target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1. 动态规划思路

首先，让我们定义一个二维数组 dp，其中 dp[j][i]意义是背包容量为i的情况下，最后一个加入的数字是从nums[0]到nums[i]之间的方法的总数。我们的目标是求 dp[nums.size() - 1][target]，即使用所有的元素构成和为 target 的排列的个数。

2. 初始化

首先，我们初始化 dp 数组，将所有元素都初始化为 0。然后我们设置 dp[0][0] = 1，这是因为在前 0 个元素中，构成和为 0 的组合有一种方式，即不选择任何元素。

3. 填充动态规划数组

接下来，我们使用两个嵌套循环来填充 dp 数组。外层循环 i 表示考虑前 i 个元素，内层循环 j 表示目标和为 j。

• 如果 j < nums[i]，意味着当前的元素 nums[i] 太大，不能加入组合中，所以我们将 dp[i][j] 设置为 dp[i-1][j]，表示不选择当前元素时的组合数，继承上一行的值。

• 如果 j >= nums[i]，意味着当前的元素 nums[i] 可以加入组合中。我们需要考虑两种情况：

  • 不选择当前元素，即 dp[i][j] = dp[i-1][j]。
  • 选择当前元素，即 dp[i][j] += dp[i][j - nums[i]]，这里的 dp[i][j - nums[i]] 表示在考虑前 i 个元素，和为 j - nums[i] 的组合数。

最终，dp[nums.size() - 1][target] 就代表了使用所有元素构成和为 target 的组合的个数。

4. 返回结果

最后，我们返回 dp[nums.size() - 1][target] 即可得到答案。