[!info] related notes 算法面试题型 MOC 动态规划 背包 DP

分割等和子集

题目链接：https://leetcode.cn/problems/partition-equal-subset-sum/

题意

给你一个正整数数组，问能否把它分成两个子集，使两个子集的元素和相等。

为什么是 01 背包

总和记为 sum。如果 sum 是奇数，直接不可能。

否则问题变成：

能不能从数组里选一些数，恰好凑出 sum / 2？

每个数最多选一次，所以它是 01 背包的“恰好装满 + 可行性”模型。

状态

dp[j] 表示是否能恰好凑出和 j。

转移

对于每个数 num：

dp[j] = dp[j] || dp[j - num]

为什么倒序

因为每个数只能用一次。如果正序更新，就会让当前数在一轮里被重复使用。

边界

dp[0] = true

样例

nums = [1, 5, 11, 5]

• 总和 22
• 目标 11
• 可以选出 [11] 或 [5, 5, 1]

所以答案是 true。

JavaScript

var canPartition = function(nums) {
    const sum = nums.reduce((a, b) => a + b, 0);
    if (sum % 2 !== 0) return false;

    const target = sum / 2;
    const dp = new Array(target + 1).fill(false);
    dp[0] = true;

    for (const num of nums) {
        for (let j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }

    return dp[target];
};

易错点

• 忘记先判断总和是否为奇数
• 把 01 背包写成正序，导致一个数被重复使用