416. 分割等和子集 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/partition-equal-subset-sum/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个只包含正整数的非空数组 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
题目详细分析
- 数据范围：长度 <= 200，元素值 <= 100，总和最大 20000，target 最大 10000。O(n * target) 的 DP 可行。
- 核心约束：子集不要求连续（从原数组中任意选），每个元素只能用一次（0-1 背包）。
- 边界条件：总和为奇数直接返回 False；最大元素 > target 返回 False。
- 隐藏条件：问题等价于”是否存在一个子集的和等于总和的一半”。这是 0-1 背包的”可行性”问题——dp[j] 表示是否存在子集和为 j（布尔值）。
小白版直白理解
你有好多块石头，想分成两堆让每堆总重量一样。每块石头只能用一次。这就像你有一个背包，容量是所有石头总重量的一半，你要看能不能从石头中选一些正好填满背包。如果总重量是奇数那你直接放弃吧——两堆根本不可能相等。
解题思路
思路一：0-1 背包 DP（推荐）
核心洞察：这是一个经典的 0-1 背包问题——从数组中选若干个数，每个数选或不选，使其和等于 target（总和的一半）。dp[j] 表示是否存在和为 j 的子集。
DP 五步法：
- dp 定义：
dp[j]表示是否存在和为 j 的子集（布尔值） - 递推公式：
dp[j] = dp[j] or dp[j - num]（当前元素选或不选） - 初始化：
dp[0] = True（空集和为 0） - 遍历顺序：先元素（物品），再倒序遍历 target（保证每个元素只用一次）
- 举例验证：nums=[1,5,11,5], target=11 → dp[0]=T; num=1: dp[1]=T; num=5: dp[5]=T, dp[6]=T; num=11: dp[11]=T ✓
def canPartition(nums):
total = sum(nums)
if total % 2 != 0: # 总和为奇数，不可能平分
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True # 和为 0 总是可以的
for num in nums:
for j in range(target, num - 1, -1): # 倒序遍历，0-1 背包
dp[j] = dp[j] or dp[j - num] # 不选 or 选
return dp[target]思路二：位运算优化
用一个 bitset 表示所有可能的和，将 DP 布尔数组优化为位运算。
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
# bits 的第 j 位为 1 表示存在和为 j 的子集
bits = 1 # 初始化为 1，表示 dp[0] = True
for num in nums:
bits |= bits << num # 将所有现有和加上 num
target = total // 2
return (bits >> target) & 1 == 1思路三：DFS + 剪枝（回溯法）
将 nums 从大到小排序，DFS 搜索是否能凑出 target，配合剪枝。
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
nums.sort(reverse=True) # 从大到小排序加速剪枝
if nums[0] > target: # 最大元素超过 target
return False
n = len(nums)
def dfs(idx, remain):
if remain == 0:
return True
if idx >= n or remain < 0:
return False
# 选择当前元素 或 跳过当前元素
return dfs(idx + 1, remain - nums[idx]) or dfs(idx + 1, remain)
return dfs(0, target)易错点
- 总和奇偶判断：必须先用
sum % 2判断，奇数和无法平分。 - 0-1 背包倒序遍历：这是最关键的区别！正序遍历会错误地变成”完全背包”（同一元素多次使用）。
- target 可能比最大元素小：如果最大元素 > target，可以直接返回 False。
- dp[0] = True：空子集的和总是 0，这是递推的基础。
框架提炼
0-1 背包可行性模板：
def zero_one_knapsack_feasible(nums, target):
dp = [False] * (target + 1)
dp[0] = True
for num in nums: # 遍历物品
for j in range(target, num - 1, -1): # 倒序遍历容量
dp[j] = dp[j] or dp[j - num] # 不选或选
return dp[target]0-1 背包与完全背包的遍历顺序对比：
| 类型 | 内层遍历 | 含义 |
|---|---|---|
| 0-1 背包 | 倒序 | 每个物品只用一次 |
| 完全背包 | 正序 | 每个物品无限用 |
关联题目
- 322-零钱兑换 — 完全背包，注意与 0-1 背包的遍历顺序区别
- 279-完全平方数 — 完全背包，求最小值
- 698-划分为 k 个相等的子集 — 本题的 K 分割进阶版
- 494-目标和 — 0-1 背包求方案数