HHot 100C++ 图解

416. 分割等和子集

中等 动态规划(一维) 3 帧动画 在力扣上做

一句话套路0-1 背包判定,一维数组必须逆序

题目描述

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

 

示例 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

思路

时间O(n·target)
空间O(target)

转化

能不能选出若干个数,和恰好为 sum/2(sum 为奇数直接 false)-> 0-1 背包判定。

一维 dp[j] = 「和为 j 是否可达」。

【最重要的细节】内层容量必须逆序遍历

正序会让 dp[j-w] 在本轮刚被更新过,等于同一个数用了两次(变成完全背包)。

剪枝

j 的上界取 min(target, 已扫过元素之和),避免无意义遍历。

图解

3 0 3 1 3 2 3 3 4 4
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/15_dp.cpp21 行
namespace lc0416 {
class Solution {
 public:
  bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2) return false;
    int target = sum / 2;
    vector<char> dp(target + 1, false);
    dp[0] = true;
    int reach = 0;  // 目前能凑出的最大和
    for (int w : nums) {
      if (w > target) return false;  // 单个数就超过一半,直接失败
      for (int j = min(target, reach + w); j >= w; --j)  // 逆序!
        if (dp[j - w]) dp[j] = true;
      reach += w;
      if (dp[target]) return true;
    }
    return dp[target];
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q416_partition_equal_subset_sum13 行
lc0416::Solution s;
vector<int> a{1, 5, 11, 5};
CHECK_TRUE(s.canPartition(a));   // 11 == 1+5+5
vector<int> b{1, 2, 3, 5};
CHECK_FALSE(s.canPartition(b));  // sum=11 奇数
vector<int> c{1, 1};
CHECK_TRUE(s.canPartition(c));
vector<int> d{100};
CHECK_FALSE(s.canPartition(d));
vector<int> e{2, 2, 1, 1};
CHECK_TRUE(s.canPartition(e));
vector<int> f{3, 3, 3, 3, 4};  // 需要「同一个数只用一次」才能过,逆序写错就真阳性
CHECK_FALSE(s.canPartition(f));

↑↓ 选择↵ 打开/ 随时唤起