416. 分割等和子集

LeetCode 416¹ · 中等 · 动态规划

题

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

例：nums = [1, 5, 11, 5] → true（[1, 5, 5] 和 [11]）；nums = [1, 2, 3, 5] → false。

一句话

总和为奇数直接不行；否则问题等价于「能否挑出一些数，和恰好为 sum / 2」——0-1 背包的可行性版本。

关键技巧

问题转化。 两半相等 ⇔ 其中一半的和是 \(S/2\)。于是只需判断子集和 \(S/2\) 是否可达。

0-1 背包，布尔型。

• 状态：\(f[t]\) = 用已考虑过的数，能否凑出和 \(t\)。
• 转移：考虑数 \(x\) 时，\(f[t] \mathrel{|}= f[t - x]\)。
• 初值：\(f[0] = \text{True}\)。
• 顺序：外层遍历数，内层 \(t\) 从 \(S/2\) 倒序到 \(x\)。

为什么内层要倒序。 一维数组里 \(f[t-x]\) 必须是「还没考虑 \(x\)」的旧值。倒序时，\(t - x < t\) 还没被本轮改过；正序的话 \(f[t-x]\) 可能刚被 \(x\) 更新过，等于 \(x\) 被用了两次——那就成了完全背包（322. 零钱兑换 恰好要正序）。

剪枝。 最大元素超过 \(S/2\) 直接失败；\(f[S/2]\) 一旦为真就可以提前返回。

位运算写法。 把 \(f\) 压成一个大整数 bits，第 \(t\) 位表示和 \(t\) 可达：bits |= bits << x。Python 大整数移位很快，常数小得多。

解

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        f = [True] + [False] * target
        for x in nums:
            for t in range(target, x - 1, -1):  # 倒序：每个数只用一次
                f[t] = f[t] or f[t - x]
            if f[target]:
                return True
        return f[target]

class Solution2:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        bits = 1  # 第 t 位为 1 表示和 t 可达
        for x in nums:
            bits |= bits << x
        return bool(bits >> (total // 2) & 1)

延伸

• 完全背包对照：322. 零钱兑换、279. 完全平方数——物品可重复，内层正序。
• 目标和（LeetCode 494）：给每个数加正负号凑 target，同样化成子集和 \((S + \text{target})/2\)，求方案数。
• 坑：别用 t 从 0 开始正序，自测里 [1, 2, 5] 这种会被「同一个 1 用两次」误判。

for S in (Solution, Solution2):
    s = S()
    assert s.canPartition([1, 5, 11, 5]) is True
    assert s.canPartition([1, 2, 3, 5]) is False
    assert s.canPartition([1]) is False
    assert s.canPartition([2, 2]) is True
    assert s.canPartition([1, 2, 5]) is False