416. 分割等和子集

题目描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1,5,5] 和 [11]

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

---

解题思路

第一步：理解问题本质

这道题可以转化为一个经典的0/1 背包问题：

1. 计算数组总和 sum
2. 如果 sum 是奇数，无法平分，直接返回 False
3. 问题转化为：能否从数组中选出一些数，使它们的和等于 sum / 2

这就是 0/1 背包问题：背包容量为 target = sum / 2，每个物品（数字）可以选或不选，问能否恰好装满背包。

第二步：暴力解法 - 回溯

思路： 枚举每个数字选或不选，检查是否存在一种选择使和为 target。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        # 总和是奇数时两半不可能相等，直接排除，省掉整棵搜索树
        if total % 2:
            return False
        # 只需要凑出一半，另一半自然就是剩下的数
        target = total // 2
        n = len(nums)

        # backtrack(i, current_sum)：考虑第 i 个数时，手里已选出 current_sum 的和
        def backtrack(i, current_sum):
            # 恰好凑满，说明找到了一个合法的子集
            if current_sum == target:
                return True
            # 已经超出目标（数都是正数，继续加只会更大）或没数可选了
            if current_sum > target or i >= n:
                return False
            # 选或不选第 i 个数
            # 两条分支任意一条成功即可，所以用 or 连接并短路
            return backtrack(i + 1, current_sum + nums[i]) or \
                   backtrack(i + 1, current_sum)

        # 从第 0 个数、和为 0 开始搜索
        return backtrack(0, 0)

为什么不够好？ 时间复杂度 O(2^n)，会超时。

第三步：优化解法 - 记忆化搜索

关键洞察： 递归过程中有大量重复子问题，如 dfs(2, 10) 可能被多次计算。

优化： 用 @cache 缓存已经计算过的状态。

from functools import cache

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        # 奇数总和无法平分，先挡住，避免后面白算
        if total % 2:
            return False
        target = total // 2
        n = len(nums)

        # dfs(i, remain)：从第 i 个数开始选，还能不能恰好凑出 remain
        @cache
        def dfs(i, remain):
            # 剩余额度为 0，这条路走通了
            if remain == 0:
                return True
            # 额度变负（负数不能再加回来）或已经没数可选
            if remain < 0 or i >= n:
                return False
            # 选第 i 个数就扣掉它的值，不选就跳过；任一成功即可
            return dfs(i + 1, remain - nums[i]) or dfs(i + 1, remain)

        # 从第 0 个数开始，凑出 target 即可
        return dfs(0, target)

第四步：最优解法 - 动态规划

关键洞察： 这是标准的 0/1 背包问题，可以用 DP 解决。

状态定义： dp[j] 表示能否用数组中的数凑出和为 j

状态转移：

dp[j] = dp[j] or dp[j - nums[i]]

• dp[j]：不选第 i 个数
• dp[j - nums[i]]：选第 i 个数

空间优化： 使用一维数组，倒序遍历避免重复计算。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        # 总和为奇数时不存在平分方案
        if total % 2:
            return False

        target = total // 2
        # dp[j] 表示能否凑出和为 j；和为 0 天然成立，其余先当作凑不出
        dp = [True] + [False] * target

        for num in nums:
            # 倒序：保证 dp[j - num] 还是「上一轮」的旧值，
            # 即本轮不会重复使用 num（0/1 背包的关键）
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]
            # 提前收工：目标已经可达，后面的数不用再看
            if dp[target]:
                return True

        # 所有数都用完仍没凑出 target
        return dp[target]

---

完整代码实现

算法可视化 · 逐帧回放这道题的代码29 帧 · 录制输入 [1,5,11,5]

from typing import List
from functools import cache

class Solution:
    """
    分割等和子集 - 记忆化搜索解法

    核心思路：
    1. 计算数组总和，如果是奇数直接返回 False
    2. 问题转化为：能否凑出和为总和一半的子集
    3. 使用记忆化搜索，dfs(i, remain) 表示从第 i 个数开始能否凑出 remain

    时间复杂度: O(n * target)
    空间复杂度: O(n * target)
    """
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False

        target = total // 2
        n = len(nums)

        @cache
        def dfs(start: int, remain: int) -> bool:
            if remain == 0:
                return True
            if remain < 0 or start >= n:
                return False
            return dfs(start + 1, remain - nums[start]) or \
                   dfs(start + 1, remain)

        return dfs(0, target)

---

示例推演

以 nums = [1, 5, 11, 5] 为例：

第一步：预处理

• 总和 = 1 + 5 + 11 + 5 = 22
• target = 11

第二步：DP 过程

步骤	当前数字	dp 数组（下标 0-11）
初始	-	[T,F,F,F,F,F,F,F,F,F,F,F]
1	1	[T,T,F,F,F,F,F,F,F,F,F,F]
2	5	[T,T,F,F,F,T,T,F,F,F,F,F]
3	11	[T,T,F,F,F,T,T,F,F,F,F,T]
4	5	[T,T,F,F,F,T,T,F,F,F,T,T]

结果： dp[11] = True，可以分割

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力回溯	O(2^n)	O(n)	枚举所有子集
记忆化搜索	O(n × target)	O(n × target)	target = sum/2
动态规划	O(n × target)	O(target)	空间优化版

说明：

• n 是数组长度
• target 是数组总和的一半
• 由于 nums[i] <= 100 且 n <= 200，target <= 10000，DP 完全可行

---

易错点总结

1. 总和为奇数的判断

# 必须先判断总和是否为奇数：两半都是整数和，奇数不可能平分
if sum(nums) % 2:
    return False

2. DP 数组的遍历方向

# 必须倒序遍历！
for j in range(target, num - 1, -1):
    dp[j] = dp[j] or dp[j - num]

# 正序遍历会导致重复计算（完全背包）
# 因为正序时 dp[j - num] 已被本轮更新过，同一个 num 可能被用多次

3. 递归的边界条件

# 注意判断顺序
if remain == 0:      # 先判断是否凑出目标
    return True
if remain < 0:       # 再判断是否超出
    return False
# 顺序很关键：先认下「已经凑满」，再排除「走不通」，否则成功的一层会被误判

---

扩展思考

1. 如何输出具体的分割方案？

可以用 DP 记录路径，或使用回溯记录选择的数字。

2. 如果要求两个子集的大小也相等？

需要二维 DP：dp[i][j] 表示能否用 i 个数凑出和为 j。

3. 相关题目

• 494. 目标和 - 变形背包问题
• 1049. 最后一块石头的重量 II - 类似的分割问题
• 474. 一和零 - 二维费用背包

---

相关题目

• 494. 目标和
• 1049. 最后一块石头的重量 II
• 474. 一和零