📝 题目描述

题目链接：分割等和子集

给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例：

1
2
3
4
5
6
7
8
9
10
11
示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

💡 解题思路

方法一：经典背包模板

先来回顾一下什么是传说中的背包问题：有 N 件物品和一个最多能容纳重量 W 的背包；第 i 件物品的重量是 weight[i]，价值是 value[i]；求解将哪些物品装入背包里物品价值总和最大；其中，如果每个物品能拿取无限多次，则叫作完全背包问题，若每个物品仅能拿取一次，则叫作01背包问题。

再来看这个题目，我们可以转化一下，先求出所有元素的和 sum，如果 sum 是偶数，我们令 target = sum/2，则问题转化为：

nums 数组代表物品集合，每个物品的重量是 nums[i]，价值也是 nums[i]，求背包容量为 target 时，能拿取的物品都最大价值总和是多少，如果能拿取的最大的价值总和也为 target，则可以返回 true。

也就是转化为了经典的01背包问题。

我们先按照经典的01背包问题模板做一下这道题目。

经典的01背包问题，我们可以采用二维基础解法：用 dp[i][j] 记录状态，行（也就是 i）代表物品，列（也就是 j）代表背包容量，逐步填表推导。

在开始讲解之前，先处理一下本题目的特殊情况：

1、先求出所有元素的和 sum 时，如果 sum 是奇数，则肯定不能分为两个相等的子集，直接返回 false 即可；
2、在求出所有元素的和 sum 时，我们可以同时记录一下数组中的最大元素 max_item，如果 max_item > target，也就是大于所有元素和的一半，那么无论将 max_item 放到两个结果集合中的任意一个，都会导致其大于所有元素和的一半，自然也无法满足题目结果，，直接返回 false 即可。

然后我们解释一下 dp[i][j] 的含义，其表示从前 i 个物品（注意i = 0 表示前 0 个物品，也就是不拿任何物品）中进行选择，在背包容量限制为 j 的情况下可拿走的物品的最大价值。

在定义状态之后，需要考虑边界情况。以下两种情况都属于边界情况。

  • 当 i = 0 时，表示前 0 个物品可以被选取，也就是不能选取任何物品，因此 dp[0][j] = 0；
  • 题目中规定所有物品的重量都大于等于 1，那么如果背包容量 j = 0，则无法容纳任何物品，因此对于所有 0≤i≤n，都有 dp[i][0] = 0。

那么对于 i>0 且 j>0 的一般情况，如何确定 dp[i][j] 的值？对于第 i 个物品，面对当前的背包容量 j，我们只有两种选择：

  • 不放第 i 个物品（或者背包容量根本不够装，即 j < nums[i]）：此时的最大价值等同于在前 i-1 个物品中选的最大价值：

dp[i][j]=dp[i−1][j]dp[i][j] = dp[i-1][j]

  • 放入第 i 个物品（前提是容量足够，即 j >= nums[i]）：我们需要先在背包中腾出 nums[i] 的空间，此时的最大价值等于前 i-1 个物品在容量为 j-nums[i] 时的最大价值，再加上当前物品的价值 nums[i]。

dp[i][j]=dp[i−1][j−nums[i]]+nums[i]dp[i][j] = dp[i-1][j-nums[i]] + nums[i]

综合起来，状态转移方程为：

dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−nums[i]]+nums[i])dp[i][j] = \max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i])

最后，我们查看 dp[n][target] 的值是否等于 target，即可得到答案。

方法二：优化背包模板

首先，我们可以更换 dp 数组存储的数据类型，我们只需要存储 true 或 false 即可，没有必要存储具体的数值。

其次，可以发现在计算 dp 的过程中，每一行的 dp 值都只与上一行的 dp 值有关，因此只需要一个一维数组即可将空间复杂度降到 O(target)O(target)。此时的转移方程为：

dp[j]=dp[j]∣dp[j−nums[i]]dp[j]=dp[j] ∣ dp[j−nums[i]]

这时，dp 的语意为：dp[j] 表示从前 i 个物品中任意挑选，能否凑出恰好为 j 的和，上述的状态转移方程可以理解为，想知道当前能否凑出和为 j，只需看以下两种情况只要有一种成立即可：

  • 不选当前数字 num： 在之前的数字中，就已经能凑出 j 了（即旧的 dp[j] 为 true）。
  • 选当前数字 num： 在之前的数字中，能够凑出 j - num（即旧的 dp[j - num] 为 true），那么加上当前的 num，自然就能凑出 j 了。

且需要注意的是第二层的循环我们需要从大到小计算，因为如果我们从小到大更新 dp 值，那么在计算 dp[j] 值的时候，dp[j−nums[i]] 已经是被更新过的状态，不再是上一行的 dp 值。

🔧 代码实现

1、经典背包模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0, target = 0, max_item = INT_MIN, n = nums.size();
        // 求出所有元素的和
        for (auto& num : nums) {
            sum += num;
            max_item = max(max_item, num);
        }
        target = sum/2;
        // 快速判定无法分割的条件
        if ((sum %2 != 0) || (max_item > target)) {
            return false;
        }
        // 初始化dp数组
        vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
        // 开始填充dp数组
        for (int i = 1; i <=n; i++) {
            // 这里要提前注意，题目给的nums从0开始
            int num = nums[i - 1];
            for (int j = 0; j <= target; j++) {
                if (j < num) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - num] + num);
                }
            }
        }
        return dp[n][target] == target;
    }
};

2、优化背包模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0, target = 0, max_item = INT_MIN, n = nums.size();
        // 求出所有元素的和
        for (auto& num : nums) {
            sum += num;
            max_item = max(max_item, num);
        }
        target = sum/2;
        // 快速判定无法分割的条件
        if ((sum %2 != 0) || (max_item > target)) {
            return false;
        }
        // 初始化dp数组
        vector<bool> dp(target + 1, false);
        // 当容量为0时，价值自然也为0，故为true
        dp[0] = true;
        // 开始填充dp数组
        for (int num : nums) {
            // 这里必须要从大到小遍历
            for (int j = target; j >= 0; j--) {
                if (j < num) {
                    dp[j] = dp[j];
                } else {
                    dp[j] = dp[j] || dp[j - num];
                }
            }
        }
        return dp[target];
    }
};

📊 复杂度分析

1、经典背包模板

  • 时间复杂度：O(n×target)O(n \times \text{target})，其中 n 是数组的长度，target 是整个数组的元素和的一半。需要计算出所有的状态，每个状态在进行转移时的时间复杂度为 O(1)O(1)。
  • 空间复杂度：O(n×target)O(n \times \text{target})，空间复杂度取决于 dp 数组，需要额外的 n×targetn \times \text{target} 二维数组来存储计算状态。

2、优化背包模板

  • 时间复杂度：O(n×target)O(n \times \text{target})，其中 n 是数组的长度，target 是整个数组的元素和的一半。需要计算出所有的状态，每个状态在进行转移时的时间复杂度为 O(1)O(1)。
  • 空间复杂度：O(target)O(\text{target})，空间复杂度取决于 dp 数组，需要额外的 target\text{target} 一维数组来存储计算状态。

🎯 总结

  • 核心思想：学会经典的01背包问题的模板解法，以及记住题目的思路转换方法，把分割集合转换为背包问题。