LeetCode 416. 分割等和子集

◎

本节目标

将等和划分转成 01 背包可达性，并以倒序更新防止重复取数。

返回背包模型框架

查看 LeetCode 原题

题意与约束

判断数组能否分为和相等的两组，每个数字最多使用一次。

第一反应与重复子问题

总和为奇数直接失败；否则只需判断是否能选出和为 sum/2 的子集。

状态定义与转移推导

dp[j] 表示能否凑出和 j。初始化 dp[0]=true，对每个 num 倒序更新 dp[j] |= dp[j-num]。

正确性依据

倒序让 dp[j-num] 来自处理当前数字前，故当前数字只能出现一次；所有选与不选的子集由或运算覆盖。

样例执行过程

[1,5,11,5] 的目标为 11，处理到 11 时直接可达；[1,2,5] 总和虽为偶数，但目标 4 不可达。

代码实现

C++

C++17

#include <numeric>
#include <vector>
using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
};

Python

Python 3

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for num in nums:
            for capacity in range(target, num - 1, -1):
                dp[capacity] = dp[capacity] or dp[capacity - num]
        return dp[target]

复杂度分析

时间 O(n·sum)，空间 O(sum)，其中 sum 指总和的一半。

边界与易错点

• 单元素不能分为两组。
• dp[0] 必须为真。
• 正序会把一个数字重复使用。

模式迁移

这是“是否可达”的 01 背包；可迁移到目标和、石头重量等二值选择题。