题目要求

给定一个只包含正整数的数组 nums，判断能不能把所有元素分成两个子集，使两个子集的元素总和相等。

输入与输出

  • 输入：整数数组 nums
  • 输出：如果能平分，返回 True；否则返回 False
  • 每个元素必须放入两个子集之一，不能丢弃，也不能把同一个元素使用两次

示例

输入：nums = [1,5,11,5]
输出：True
解释：[1,5,5] 和 [11] 的总和都是 11

输入：nums = [1,2,3,5]
输出：False
解释：总和是 11，奇数不能平分

输入：nums = [1,1]
输出：True
解释：两个子集分别拿一个 1

约束

按 LeetCode 416 题面：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
  • sum(nums) <= 20000

Step 1：先排除总和为奇数的数组

先问一个还不涉及选数的问题：两个整数子集的和相等时，整个数组的总和必须满足什么条件？

问题压力

看 nums = [1,2,3,5]。它的总和是 11。如果两个子集的和都叫 x，那么必须有：

2 * x = 11

整数 x 不可能满足这个等式，所以这个输入可以在尝试任何选数之前直接判定为 False。

当前基线

当前只有题目合同：我们知道每个元素最终只能归入一个子集，但还没有记录“选了哪些元素”，也没有办法处理总和为偶数的实例。

断点

如果总和是奇数，继续搜索只是在做必定失败的工作；但如果总和是偶数，仅凭奇偶性还不知道是否真的存在一个子集能拿到一半总和。

在上一版基础上加入奇偶性门槛

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1:
        return False

    target = total // 2

    # 这里只把目标值算出来；下一步才判断 target 是否可达。
    # 这个占位返回值不是偶数总和实例的最终答案。
    return False

检查这次变化

assert can_partition([1, 2, 3, 5]) is False

对 [1,2,3,5]，total % 2 == 1，函数在进入任何选数逻辑前就返回 False。而 [1,1] 的 target 会被算成 1，只是当前版本还没有判断这个 1 能不能由元素凑出来。

当前版本冻结点

现在这个版本能：

  • 根据总和奇偶性排除必不可能的输入。
  • 把偶数总和转换成一个待验证的目标值 target = total // 2。

它还缺：

  • 判断某个元素子集能否恰好达到 target。
  • 处理所有总和为偶数的真实输入；偶数分支的 return False 仍是占位。

下一步要把“大问题”缩成一个更小的问题：处理完数组前缀后，哪些子集和已经可达？

Step 2：记录处理前缀后哪些和可达

问题压力

[1,1] 的总和是 2，所以目标是 1。奇偶性检查只能告诉我们“值得继续”，却没有回答：看到第一个 1 后，能不能得到 1？看到第二个 1 后，又有哪些和可以得到？

把过程写小一点：

已处理的元素当前可达的和
还没处理{0}
第一个 1{0, 1}
两个 1{0, 1, 2}

这里的较小问题是：处理完数组的一个前缀后，所有只使用这个前缀、且每个元素最多用一次的和，组成什么集合？

当前基线

Step 1 已经能算出偶数总和对应的 target，但偶数分支最后仍然是占位的 return False。当前版本没有保存任何“已经能凑出的和”。

断点

如果直接只盯着 target，会看不见中间状态。例如 [1,5,11,5] 的目标是 11，需要先知道前缀能形成哪些较小的和，才能判断后面的 11 或两个 5 是否能接上。

在上一版本中替换占位返回

先用一个集合保存可达和。处理一个 num 时，分成两条路：跳过它，或把它加到上一轮的每个和上。为了保证当前元素只处理一次，新的集合从旧集合复制出来，再交给下一轮。

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1:
        return False

    target = total // 2
    reachable = {0}

    for num in nums:
        next_reachable = set(reachable)

        for current in reachable:
            new_sum = current + num
            if new_sum <= target:
                next_reachable.add(new_sum)

        reachable = next_reachable

    return target in reachable

检查这次变化

先走 [1,1]：

reachable = {0}
读入第一个 1 -> {0,1}
读入第二个 1 -> {0,1,2}
target = 1，所以返回 True

再用三个输入做可执行检查：

assert can_partition([1, 5, 11, 5]) is True
assert can_partition([1, 2, 3, 5]) is False
assert can_partition([1, 1]) is True

当前版本冻结点

现在这个版本能：

  • 把“能否平分”改写成“目标 target 是否出现在可达和集合中”。
  • 通过复制旧集合，明确每个数组元素只在一轮里被处理一次。
  • 用一个可运行的 baseline 通过三个代表性例子。

它还缺：

  • 一个有固定边界、含义更稳定的状态表，来清楚表达“前缀 + 和”的关系。
  • 对集合复制成本的控制，以及后续压缩状态时如何保持每个元素只能使用一次。

下一步把这个集合状态写成二维表，先得到一版完整、但还没有压缩空间的正确转移。

Step 3：把“前缀 + 和”写成二维状态

问题压力

集合 baseline 已经能给出答案，但它有一个新问题：每读入一个数字，都要复制并扩展一整个集合；当 target 变大时，集合的内容和大小都在动态变化。我们还很难直接检查“处理到第几个元素时，某个和为什么可达”。

例如 [1,5,11,5] 的目标是 11。集合版本会依次产生很多中间和，但我们真正想问的是一组固定问题：只看前 i 个元素，是否能凑出和 s？

当前基线

Step 2 的 reachable 集合保存了前缀的所有可达和；每一轮都从旧集合复制出 next_reachable，再加入选择当前元素得到的新和。

断点

集合版本的答案是对的，却没有一个固定的坐标去表达“第 i 个元素”和“目标和 s”之间的关系。若要把每个前缀状态都保留下来，就需要把这两个维度明确写出来。

在上一版本中替换状态表示

现在才给这个固定的“每个元素选或不选一次”的状态一个名字：二维 dp[i][s]。它表示：只使用 nums[0] 到 nums[i-1] 时，是否能凑出和 s。

先放入不选任何元素的 base case：dp[0][0] = True。处理第 i 个元素 num = nums[i - 1] 时只有两条来源：

  • 不选 num：沿用 dp[i - 1][s]。
  • 选 num：只有 s >= num 时，才能从上一行的 dp[i - 1][s - num] 接过来。
def can_partition(nums: list[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1:
        return False

    target = total // 2
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = True

    for i in range(1, n + 1):
        num = nums[i - 1]

        for s in range(target + 1):
            dp[i][s] = dp[i - 1][s]
            if s >= num:
                dp[i][s] = dp[i][s] or dp[i - 1][s - num]

    return dp[n][target]

检查这次变化

对 [1,1]、target = 1，只观察目标列可以得到：

i（已处理个数）dp[i][0]dp[i][1]
0TrueFalse
1TrueTrue
2TrueTrue

每次“选入”都读取上一行，所以第二个 1 不会在同一行里再次制造一个新的 1。再运行代表性案例：

assert can_partition([1, 5, 11, 5]) is True
assert can_partition([1, 2, 3, 5]) is False
assert can_partition([1, 1]) is True
assert can_partition([2]) is False
assert can_partition([2, 2]) is True

当前版本冻结点

现在这个版本能：

  • 用 dp[i][s] 明确表示每个前缀的可达和。
  • 用上一行同时表达“跳过当前元素”和“选入当前元素”，得到第一版完整正确解。
  • 通过主例子和单元素/双元素边界。

它还缺：

  • 二维表的额外空间是 O(n * target)，但每一行其实只依赖上一行。
  • 如果把行压成一维，更新方向必须继续保护“每个元素只能使用一次”。

下一步先尝试一维压缩，再用一个反例找出正向更新为什么会重复使用当前元素。

Step 4：一维压缩后，正向更新会偷用同一个元素

问题压力

Step 3 的二维表中，第 i 行只依赖第 i - 1 行，所以看起来可以只保留一行。这样能把空间从 O(n * target) 降下来，但一旦把新结果写回同一个数组，就必须决定和 num 有关的和要按什么方向处理。

当前基线

当前基线是二维正确版本：选入 num 时读取上一行的 dp[i - 1][s - num]。压成一维后没有“上一行”这个物理副本了，最直接的尝试是让 s 从小到大走。

断点

正向走时，dp[s - num] 可能已经在**本轮处理同一个 num**时被写成 True。这会把一个元素重复使用，破坏题目“每个元素只能放一次”的约束。

在上一版本中替换为一维正向版本

这里只改变状态存储和循环方向，先保留最直觉的正向写法：

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1:
        return False

    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(num, target + 1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

检查这次变化

反例是 nums = [1,1,4]，总和为 6，目标是 3。正确答案应为 False：两个 1 只能凑出 2，4 又超过目标。

但正向处理第一个 1 时，数组变化是：

初始：      [True, False, False, False]
s = 1：     [True, True,  False, False]  # 用了一个 1
s = 2：     [True, True,  True,  False]  # 读到本轮刚写入的 dp[1]
s = 3：     [True, True,  True,  True]   # 又读到本轮刚写入的 dp[2]

于是这个失败版本会把一个 1 当成三个 1 使用，返回 True。二维版本在同一输入上返回 False；因此这里的 True 是 bug 证据，不是题目答案。

当前版本冻结点

现在这个版本能：

  • 展示为什么二维表可以被压成一维数组。
  • 用具体轨迹定位正向更新造成的同轮重复使用。

它还缺：

  • 让 dp[s - num] 在本轮仍代表“加入当前元素之前”的状态。
  • 一个真正满足 0/1 语义、能通过 [1,1,4] 的更新方向。

下一步只改 s 的遍历方向，检查倒序是否恢复上一行语义。

Step 5：倒序遍历，恢复每个元素只能用一次

问题压力

Step 4 的反例已经把问题缩到一个地方：一维数组没有保存上一行，正向循环会读到本轮刚写入的状态。我们不需要再换状态定义，只需要让较小的和在本轮还没有被改写。

当前基线

当前基线是正向版本：

for num in nums:
    for s in range(num, target + 1):
        dp[s] = dp[s] or dp[s - num]

断点

当 s 从小到大走时，s - num 小于 s，所以它可能已经包含当前 num。[1,1,4] 中的第一个 1 就因此被重复使用，错误地把目标 3 标成可达。

在上一版本中只替换遍历方向

把 s 从 target 向下走到 num：

for num in nums:
    for s in range(target, num - 1, -1):
        dp[s] = dp[s] or dp[s - num]

为什么这一次不会重用当前元素？处理 s 时，s - num 更小；倒序循环还没有访问到更小的位置，所以 dp[s - num] 仍是本轮开始前的值，相当于二维表里的上一行。

把这个唯一变化放回完整函数：

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1:
        return False

    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

检查这次变化

先重跑 Step 4 的反例：

assert can_partition([1, 1, 4]) is False

再覆盖主例子和边界：

assert can_partition([1, 5, 11, 5]) is True
assert can_partition([1, 2, 3, 5]) is False
assert can_partition([1, 1]) is True
assert can_partition([2]) is False
assert can_partition([2, 2]) is True

在每个 num 的一轮结束时，dp[s] 表示“已经处理过的元素中，是否存在一个子集能凑出 s”。倒序只改变写入顺序，不改变这个状态含义；它保证本轮读取的较小和还没有把当前元素算进去。

复杂度

令 target = sum(nums) // 2。每个元素最多扫描 target 个和，因此时间复杂度是 O(n * target)；只保留一个目标和数组，额外空间是 O(target)。

当前版本冻结点

现在这个版本能：

  • 用一维状态正确完成 0/1 选择，每个元素最多使用一次。
  • 通过正向版本的反例、主例子和边界测试。
  • 以 O(n * target) 时间和 O(target) 额外空间返回最终答案。

它还缺：

  • 把不变量、边界条件和“为什么不能正向遍历”集中复盘，方便以后迁移到其他背包题。

下一步只补正确性与边界说明，不再改变算法代码。

正确性与边界

循环不变量

处理完前 k 个元素后，对每个 s，dp[s] 的含义是：只从这 k 个元素中选取、且每个元素最多一次，能否凑出总和 s。

  • 初始时还没有处理元素，只有空子集的和 0 可达，所以 dp[0] = True，其余位置为 False。
  • 处理一个新元素 num 时，dp[s] 可以保持原值，表示跳过 num；也可以从 dp[s - num] 转为 True，表示选入 num。
  • s 从大到小更新，读取的 dp[s - num] 还没有在本轮被当前 num 改写，因此它只来自前 k 个元素。这正是二维转移中“读取上一行”的含义。

因此每轮结束后，不变量仍然成立。所有元素处理完时，dp[target] 恰好回答“是否存在一个子集的和等于总和的一半”。

边界检查

下面这些情况覆盖了最容易错的分支：

输入结果检查点
[1]False总和为奇数，提前返回
[2]False总和为偶数，但唯一元素无法凑出目标 1
[1,1]True两个相同元素各使用一次
[2,2]True目标 2 由一个元素达成
[1,1,4]False不能把一个 1 在同一轮重复使用
[1,2,3,5]False奇数总和门槛
[1,5,11,5]True标准可分割实例

题目约束规定 nums 非空且元素为正整数，所以这里不额外引入空数组或零元素分支；边界说明与题面范围保持一致。

常见误区

  • 把内层循环写成 range(num, target + 1)：这是允许同一个元素在一轮中反复使用的正向更新，适合完全背包语义，不适合本题的 0/1 语义。
  • 倒序范围写成 range(target, num, -1)：这样会漏掉 s == num，应写成 range(target, num - 1, -1)。
  • 只检查总和是否为偶数：偶数只是必要条件，仍必须验证 target 是否可达。

小结

这道题的路线可以压缩成四个连续问题：

  1. 总和为奇数时，直接排除。
  2. 总和为偶数时，把问题改写为“能否凑出 target”。
  3. 每个元素只有选或不选一次，因此状态是 0/1 选择。
  4. 一维压缩后必须倒序遍历，才能让本轮读取的状态仍来自上一轮。

最终要记住的不是一行模板，而是这条因果关系：元素只能使用一次 -> 一维状态不能读取本轮刚写入的位置 -> 和的循环必须倒序。