LeetCode LCR 101. 分割等和子集

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 简单 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 101. 分割等和子集

题意分析

给一个只含正整数的数组 nums，问能不能把它拆成两个互不相交的子集，使两边元素之和相等。返回的是布尔值，不需要给出具体的划分方案，这一点决定了我们只需要判断「可达性」，不必记录路径。

「两边和相等」立刻可以化简：设总和为 $S$，则每一边必须恰好等于 $S/2$。于是问题从「二分数组」变成了「从数组里挑若干个数，使它们的和恰好等于 $S/2$」。原来的两个自由度被压成了一个。

约束里透露的信号非常明确：数组长度不超过 200，每个元素不超过 100，所以 $S \le 20000$，$S/2 \le 10000$。目标和是一个被数值上界卡死的小整数——这正是「用和当下标、按物品逐个决策」的典型信号。如果只看子集个数，那是 $2^{200}$ 的规模，完全不可枚举；但按和归并之后，状态只有一万个。

每个元素只有「选」或「不选」两种可能，而且每个元素最多用一次。这个「一次」的限制是后面所有实现细节（尤其是遍历方向）的根源。

边界上要注意三件事：$S$ 是奇数时不可能均分，必须直接否定；数组只有一个元素时无论如何都分不出两个非空的等和子集；元素全为正数保证了和是单调增长的，不必考虑负数带来的下标平移。

解法：数学推导

核心思路

暴力做法是枚举每个元素属于左边还是右边，共 $2^n$ 种分法，逐一算和比较。$n$ 取到 200 时这条路彻底走不通。

瓶颈在哪里？在于大量分法其实是等价的。我们只关心「已选元素的和」是多少，至于这个和由哪几个元素凑出来的，对后续决策毫无影响。比如 {1,5} 和 {2,4} 都得到 6，它们对剩下元素的判断能力完全一样。把和相同的分支合并，指数级的搜索树就塌缩成了一张「和的可达表」。

观察到这一点，定义就自然浮出来了。设 dp[j] 表示：在已经考察过的前若干个元素中，是否存在一个子集，其和恰好为 j。这是一个布尔值的可达性表，长度为 target + 1，其中 target = S / 2。

初始状态 dp[0] = true：一个元素都不选，和为 0 永远可达。其余 dp[j] = false。

转移：考察元素 x 时，若某个和 j - x 在加入 x 之前已经可达，那么 j 在加入 x 之后也可达。写成 dp[j] = dp[j] || dp[j - x]。等号左边的 dp[j] 是「不选 x」的继承，右边的 dp[j - x] 是「选 x」的新增。

这里必须显式写出一条不变量：在处理元素 x 的整个内层循环期间，被读到的 dp[j - x] 必须是「还没有用过 x」的那一版。因为 x 只能用一次，如果读到的是已经把 x 算进去的值，就等价于允许 x 被重复使用。要维持这条不变量，内层循环必须从大到小遍历 j——倒序时下标更小的 dp[j - x] 尚未在本轮被改写，天然还是旧值。

最终答案就是 dp[target]。

解题步骤

先求总和并判奇偶。为什么：目标是把 $S$ 平分，$S$ 为奇数时 $S/2$ 不是整数，任何整数子集和都凑不出来，直接返回 false。这一步顺带保证了后面 target = sum / 2 的整除是精确的。

令 target = sum / 2，开一个长度 target + 1 的布尔数组 dp。为什么开到 target 而不是 sum：我们只关心能否凑出一半，超过一半的和对结论没有帮助，砍掉可以把时间和空间都减半。

置 dp[0] = true。为什么：空集的和是 0，这是所有转移的唯一起点。漏掉它整张表会全是 false。

外层按元素遍历 x，内层从 j = target 递减到 j = x。为什么外层是元素、内层是容量：这样每个元素恰好被「决策」一次，符合「每个数只能用一次」的题意。为什么内层倒序：维持前面那条不变量，保证 dp[j - x] 读到的是不含 x 的旧值。为什么内层下界是 x：j < x 时 j - x 越界，且这些和根本装不下 x，本轮无需更新。

执行 dp[j] = dp[j] || dp[j - x]。为什么用「或」：只要「不选 x 已经可达」或者「选 x 后可达」中任意一条成立，j 就可达，可达性一旦为真不会被推翻。

返回 dp[target]。为什么：它的含义正是「存在一个子集其和为总和的一半」，剩下的元素之和自动也是一半。

以 nums = [1, 5, 11, 5] 走一遍。总和 $S = 22$ 为偶数，target = 11，dp 长度 12，初始只有 dp[0] = true。

处理 x = 1：j 从 11 递减到 1，只有 j = 1 时 dp[0] 为真，于是 dp[1] = true。此刻可达集合是 {0, 1}。

处理 x = 5：j 从 11 递减到 5。j = 6 时 dp[1] 为真，dp[6] = true；j = 5 时 dp[0] 为真，dp[5] = true。倒序保证了先写 dp[6] 再写 dp[5]，所以写 dp[6] 时读到的 dp[1] 还是旧值，5 没有被用两次。可达集合变成 {0, 1, 5, 6}。

处理 x = 11：j 从 11 递减到 11，dp[0] 为真，dp[11] = true。此时已经凑出 11，可达集合 {0, 1, 5, 6, 11}。

处理 x = 5：j 从 11 递减到 5，dp[11] 已是真、dp[10] = dp[10] || dp[5] = true、dp[6] 已是真、dp[5] 已是真。表继续变大但结论不变。

循环结束，返回 dp[11] = true，对应划分 {11} 与 {1, 5, 5}，两边和都是 11。

再看反例 nums = [1, 2, 3, 5]：$S = 11$ 是奇数，第一步就返回 false，一次 DP 都不用做。

代码实现

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        // 奇数无法平分，直接否定。
        if (sum % 2 != 0) {
            return false;
        }

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int x : nums) {
            // 倒序遍历，保证 dp[j - x] 读到的是尚未使用 x 的旧值。
            for (int j = target; j >= x; --j) {
                dp[j] = dp[j] || dp[j - x];
            }
        }

        return dp[target];
    }
}

func canPartition(nums []int) bool {
    sum := 0
    for _, x := range nums {
        sum += x
    }
    // 奇数无法平分，直接否定。
    if sum%2 != 0 {
        return false
    }

    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true

    for _, x := range nums {
        // 倒序遍历，保证 dp[j-x] 读到的是尚未使用 x 的旧值。
        for j := target; j >= x; j-- {
            dp[j] = dp[j] || dp[j-x]
        }
    }

    return dp[target]
}

复杂度分析

时间复杂度：$O(n \cdot S)$，其中 $n$ 是元素个数、$S$ 是总和。凭什么：外层遍历 $n$ 个元素，内层最多遍历 $S/2$ 个容量，循环体是常数次布尔运算。本题上界为 $200 \times 10000 = 2 \times 10^6$，完全可接受。

空间复杂度：$O(S)$。凭什么：只维护一个长度为 $S/2 + 1$ 的一维布尔数组，二维表被滚动掉了，与元素个数无关。

关键点总结

「把集合分成两个等和子集」永远先化简成「凑出总和的一半」，两个自由度压成一个，这是这类题的第一刀。

判断可达性时，状态里只保留「和」而丢弃「具体选了谁」，是把 $2^n$ 压成 $O(nS)$ 的关键——面试中要能主动说出「和相同的分支等价」这句话。

0-1 背包的一维写法，容量必须倒序；完全背包才正序。能当场解释「倒序是为了让 dp[j-x] 保持旧值」，比记住结论重要得多。

值域被约束卡死（sum ≤ 20000）是「用值当下标」的信号，看到「元素小、个数少、问能否凑出某个和」就该往背包方向想。

面试视角：先说暴力 $2^n$，再说「按和合并等价分支」，最后给出状态定义和转移方程，最后才写代码。面试官考的是这条推导链，不是背下来的五行循环。

这套框架可以原样迁移到「目标和」「最后一块石头的重量 II」，只需改写目标值的推导方式。

易错点总结

忘记判奇偶：nums = [1, 2, 3, 5]，sum = 11，target 被整除成 5，DP 会算出 dp[5] = true 并返回 true，而正确答案是 false。

内层容量写成正序：nums = [3, 5]，target = 4。正序时处理 x = 3 会先置 dp[3] = true，若 target 更大还会用刚更新的 dp[3] 去更新 dp[6]，等价于 3 被用了两次，把不能均分的数组判成能均分。

dp[0] 忘记置 true：整张表恒为 false，任何输入都返回 false，包括 nums = [1, 1] 这种显然成立的用例。

内层下界写成 j >= 0：x = 5、j = 2 时访问 dp[-3]，Java 抛 ArrayIndexOutOfBoundsException，Go 直接 panic。

数组开成 new boolean[target]：nums = [1, 1] 时 target = 1，数组长度为 1，最后 dp[target] 即 dp[1] 越界。长度必须是 target + 1。

把 dp[j] = dp[j] || dp[j - x] 写成 dp[j] = dp[j - x]：nums = [1, 1, 8]（sum = 10，target = 5）中已经置真的状态会被后续元素覆盖成假，可达性丢失，得到错误的 false。

外层遍历容量、内层遍历元素：nums = [3, 5]、target = 4 时，同一个容量位置会被所有元素轮流更新，元素的「只用一次」约束彻底失效，结果偏大。

误以为要返回具体划分而去记录路径：nums = [1, 5, 11, 5] 时会为了存方案额外开 $O(nS)$ 空间甚至回溯枚举，时间退化，而题目只要布尔值。

用 int 累加时担心溢出而改用复杂写法：本题 sum ≤ 20000，int 绰绰有余，画蛇添足的大数处理只会让白板代码变长出错。

相似题目

题目	难度	考察点
416. 分割等和子集	中等	与本题同题，可直接套用同一份代码
494. 目标和	中等	加减号问题先推导出正数子集和 `(sum+target)/2`，再数方案数
1049. 最后一块石头的重量 II	中等	求最接近一半的可达和，返回 `sum - 2 * best`，答案是数值而非布尔
474. 一和零	中等	0 和 1 的个数构成二维容量，倒序要同时作用在两维上
879. 盈利计划	困难	人数是上限约束、利润是下限约束，两类容量的边界处理方向相反
LCR 102. 目标和	中等	与 494 同题，本题的可达性表换成计数表