416. 分割等和子集
一句话套路0-1 背包判定,一维数组必须逆序
题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 2001 <= nums[i] <= 100
思路
时间
O(n·target)空间
O(target)转化
能不能选出若干个数,和恰好为 sum/2(sum 为奇数直接 false)-> 0-1 背包判定。
一维 dp[j] = 「和为 j 是否可达」。
【最重要的细节】内层容量必须逆序遍历
正序会让 dp[j-w] 在本轮刚被更新过,等于同一个数用了两次(变成完全背包)。
剪枝
j 的上界取 min(target, 已扫过元素之和),避免无意义遍历。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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];
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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));