LC416　分割等和子集¶

中等通过率 54.3%python3核心代码模式动态规划样例通过牛客 AC数组动态规划背包问题0-1 背包

牛客原题　源码

讲解章节：背包问题

一句话

两半相等等价于「挑出一个子集恰好凑到总和的一半」，01 背包判可达。

解题思路¶

这题考什么¶

先做模型归约。把数组分成两个和相等的子集，等价于挑出一个子集，它的和恰好是 total / 2——剩下的元素自动构成另一半，不必单独考虑。于是「分割」这个二元操作被压成了「选或不选」的一元判定。

归约之后就是标准的 01 背包可行性问题（每个数最多用一次），见背包问题。与常见的「求最大价值」不同，这里只需要布尔可达性。

状态定义：f[c] 表示在已经考虑过的那些数当中，能否挑出若干个使它们的和恰好为 c。转移方程（x 遍历每个数）：

f[c] = f[c] or f[c - x]        c 从 target 递减到 x，**倒序**

右边的两项分别是「不选 x」（沿用旧值）与「选 x」（要求 c - x 此前已可达）。初值 f[0] = True，含义是「一个数都不挑，和为 0」——这是唯一的真值来源，整张表都从它长出来。

容量倒序遍历是这题的命门。 f[c] 依赖 f[c - x]，而 c - x < c：

倒序时先算大的 c，用到的 f[c - x] 还没被本轮碰过，仍是「尚未考虑 x」的旧值，
于是 x 至多被用一次，这正是 01 背包的语义；
正序时先算小的 c，f[c - x] 可能已经在本轮被 x 更新过，
再用一次就等于把同一个 x 选了两遍，题目就变成了完全背包。

具体错在哪：nums = [1, 5]，total = 6，target = 3。正序时 x = 1 会让 f[1]、f[2]、f[3] 依次变真（相当于用了三个 1），错误地返回 True；倒序则只有 f[1] 变真，最终返回 False，才是正确答案。这与 LC322 零钱兑换恰好相反——那题的硬币可以无限取用，所以必须正序。

数据规模与复杂度¶

1 <= nums.length <= 200，1 <= nums[i] <= 100，题面保证数组非空且只含正整数。总和上界 200 * 100 = 20000，target 上界 10000。时间 O(n * target) = 200 * 10000 = 2e6 次内层迭代，本机实测最坏用例约 0.02 秒。空间 O(target)，一个长度 target+1 的布尔列表。

与之对照的暴力枚举子集是 2 的 200 次方种，天文数字，完全不可行； DP 之所以能压下来，是因为不同子集只要和相同就等价，状态数从子集数塌缩成和的取值数。

坑在哪¶

总和为奇数直接返回 False。奇数的一半不是整数，连目标值都构造不出来，不挡掉的话 total >> 1 会向下取整，算出的是一个根本不对应原问题的目标。判奇偶用 total & 1 与 total % 2 等价，前者少一次除法。
内层容量必须倒序，理由见上。这是全题最容易写反的一行，写成 range(x, target + 1) 就把 01 背包变成了完全背包。
内层下界写 x - 1（即 range(target, x - 1, -1)，取到 x 为止）。再往下 c < x 时 c - x 是负数，Python 的负下标不会报错而会静默取到表尾，算出完全错误的可达性——这是比越界崩溃更难查的一类问题。 x > target 时这个区间自然为空，不需要额外判断。
f[0] = True 不能省。它代表空子集，是整张表唯一的真值来源；设成 False 会让所有格子永远为假，任何输入都返回 False。
提前返回是安全的：f[target] 一旦为真就不会再变回假（转移只把 False 改成 True，从不反向），所以每轮结束时检查一次可以省掉后面的循环，且不影响正确性。
题面保证 nums 只含正整数。若允许 0，本写法仍正确（0 不改变任何可达性）；若允许负数，「一半」的定义与倒序背包都会失效，需要换模型。

样例复核¶

nums = [1, 5, 11, 5]，total = 22 为偶数，target = 11。

起手 f = {0}
x=1  -> 可达和集合 {0, 1}
x=5  -> {0, 1, 5, 6}
x=11 -> 倒序只有 c = 11 落在区间里，f[11] = f[0] = True

第三轮结束时提前返回 True，对应子集 [11]，另一半是 [1, 5, 5]，与题面「[1,5,5] 和 [11]」的解释一致。

参考实现¶

solutions/leetcode/LC416/sol.py
from typing import List, Optional


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        # 和为奇数时一半不是整数，两个子集不可能相等；不挡掉的话下面的整除会悄悄取整，
        # 求出的是一个不对应原问题的目标值
        if total & 1:
            return False
        target = total >> 1                 # 等价于 total // 2，位移少一次除法
        # f[c] = 在已考虑过的数里能否挑出若干个使和恰为 c。
        # f[0] = True 代表空子集，是整张表唯一的真值来源，其余从它长出来
        f = [False] * (target + 1)
        f[0] = True
        for x in nums:
            # 01 背包的命门：容量**倒序**。f[c] 依赖 f[c-x]，倒序时 f[c-x] 还没被本轮碰过，
            # 仍是「尚未考虑 x」的旧值，于是 x 至多被选一次。
            # 正序则 f[c-x] 可能已经含过 x，同一个数被重复选中，题目就变成完全背包
            # （nums = [1, 5] 会因为连用三个 1 而错误地判出 target = 3 可达）。
            # 下界取到 x 为止：c < x 时 c-x 是负数，Python 的负下标不报错却会取到表尾
            for c in range(target, x - 1, -1):
                if f[c - x]:
                    f[c] = True             # 选上 x：由「和为 c-x 可达」推出「和为 c 可达」
            # 可达性只会由假变真、从不反向，所以一旦命中就能提前收工
            if f[target]:
                return True
        return f[target]

LC416 分割等和子集¶