跳转至

416. 分割等和子集

力扣链接(中等)：https://leetcode.cn/problems/partition-equal-subset-sum

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

示例 1：

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

示例 2：

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

提示：

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

个人题解

转换为 01 背包问题

  • 要分割为两个等和子集，可以转化为在两个容量相等的背包中放价值相等的物品；
  • 每个元素只能使用一次，考虑转换为 01 背包问题；
  • 背包要放入集合中的元素，重量为元素值，价值也为元素值；
  • 如果背包正好装满，说明找到了总和为总值一半的子集。

动态规划（滚动数组）

一维数组 dp 的背包其实和二维数组逻辑相同，只不过二维数组每遍历一个物品 i 产生的每一层 dp[i][]，都会被下一层从后向前覆盖，将二维降至一维，故又称为滚动数组。请对比二维和一维 dp 遍历顺序的异同。

  1. dp[j] 表示容量为 j 的背包能够装下物品的最大价值，在本题中价值等于重量，即 dp[j] = j 代表背包刚好装满；

  2. 01 背包问题通用递推公式 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) 具体到本题应该为 dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])；

  3. 初始化 dp[0] = 0，很显然，一个容量为 0 的背包无法放入任何物品。需要注意的是，如果物品价值有负数，则还需要将数组其它部分初始化为 INT_MIN 这样才会被更大的价值覆盖，反之初始化为 0 即可；

  4. 一维数组的背包写法与二维数组不同，由于 dp[j] 依赖 dp[j - weight[i]]，为了使得每次取得状态不会和上一次重合，保证每种物品只会取得一次，所以 j 要从后向前遍历。与此同时，外层循环必须遍历物品，而不能遍历背包容量，否则每个背包 dp[j] 只能装一种物品。以下案例对 j 遍历方向进行了对比：

    Text Only
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    bag size: 4
item   weight   value
 0       1        15
 1       3        20

假设外层 for 循环枚举到物品 0：

内层 for 循环从后向前遍历 bagsize -> weight[i]：
枚举到 bagsize (4)：dp = {0, 0, 0, 0, 15}
枚举到 3：dp = {0, 0, 0, 15, 15}
枚举到 2：dp = {0, 0, 15, 15, 15}
枚举到 weight[0] (1)：dp = {0, 15, 15, 15, 15}

内层 for 循环从前向后遍历 weight[i] -> bagsize：
枚举到 weight[0] (1)：dp = {0, 15, 0, 0, 0}
枚举到 2：dp = {0, 15, 30, 0, 0}
此时已经出现问题：dp[j] = dp[2 - weight[0]] + value[0] = 15 + 15 = 30
...
    由此可见，从前向后遍历会导致 dp[j] 已经被取过一次的物品 0 再次装入背包，这不满足 01 背包的基本要求，完全背包则与之相反，在此可以手动推导一下非滚动数组为什么不存在这个问题。

    我个人针对此问题总结了一句话“常规 dp 数组是靠 dp[i - 1] 来获取上一层 dp 数组，所以不受 j 遍历顺序影响，而滚动 dp 数组则是靠 max(dp[j], dp[j - weight[i]] + value[i]) 原地获取上一层 dp 数组”，所谓上一层 dp 即指枚举物品 i - 1 完成后的 dp；

  5. 手动推导 dp 数组无误。

C++
 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
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // dp 数组大小取决于背包容量
        const int N = (200 * 100 >> 1) + 10;
        int dp[N] = {};

        // 统计总和，因为要分配到两个大小一样的背包（即子集元素和相等）
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) sum += nums[i];

        if(sum % 2 != 0) return false;
        int target = sum >> 1;

        // 转换为 01 背包问题
        // 物品重量 nums[i] 物品价值 nums[i]
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) {
                // dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        // dp[target] 代表容量为 target 的背包能装下物品的最大价值
        // target 又为 sum 的一半，所以 dp[target] == target 代表恰好能分割两个等和子集
        if(dp[target] == target) return true;
        return false;
    }
};