等和子集分割
将分割问题重新表述为目标值为总和一半的 0/1 背包问题，并使用布尔 DP 数组判断是否可行。
等和子集分割 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
问题描述
给定一个非空的正整数数组 nums，判断是否可以将其划分为两个元素和相等的子集。例如，[1, 5, 11, 5] 可以划分为 [1, 5, 5] 和 [11]，两者的元素和都是 11。如果总和为奇数，答案立即为 False。否则，需要找到一个元素和为 total_sum // 2 的子集——这是一个经典的子集和问题。
归约为子集和
关键归约是：如果总和 S 为偶数，并且某个子集的和为 S//2，那么剩余元素的和也会自动为 S//2。因此，Partition Equal Subset Sum 可以归约为：是否存在某个子集，其元素和为 S//2？ 这是经典的 NP 完全问题，即子集和问题，我们使用 0/1 背包 DP，在 O(n × S) 时间内求解。
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False # odd sum: impossible
target = total // 2
# Now: does any subset of nums sum to target?布尔型 DP 数组
定义一个布尔数组 dp[c]，其中 dp[c] = True 表示存在一个和恰好为 c 的子集。将 dp[0] = True 初始化为空集的和为 0，并将其他位置初始化为 False。对于每个数字 num，将容量从 target 递减遍历到 num（这是 0/1 背包的反向遍历），并设置 dp[c] = dp[c] or dp[c - num]。
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1): # backward: 0/1 knapsack
dp[c] = dp[c] or dp[c - num]
return dp[target]
print(canPartition([1, 5, 11, 5])) # True
print(canPartition([1, 2, 3, 5])) # False示例推演
对于 [1, 5, 11, 5]，total=22，target=11。初始时 dp[0]=True。处理 num=1 后：dp[1]=True。处理 num=5 后：dp[5]=True, dp[6]=True。处理 num=11 后：dp[11]=True（仅使用 11 本身即可）。我们已经找到 dp[11]=True，但仍会继续处理所有数字。最终答案为：dp[11]=True，因此可以完成划分。
提前终止优化
我们可以添加提前退出逻辑：如果 dp[target] 在任何时刻变为 True，就立即返回 True。这可以显著提升最佳情况下的速度。此外，如果某个元素等于 target，我们也可以立即返回 True。如果某个元素大于 target，它不可能属于和为 target 的任何子集，但我们仍然需要检查其余元素。
def canPartition_fast(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
if max(nums) > target: # any element > target makes it impossible
return False
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1):
dp[c] = dp[c] or dp[c - num]
if dp[target]:
return True # early exit
return dp[target]
print(canPartition_fast([1, 5, 11, 5])) # True使用 Python 集合替代 DP 数组
另一种方法是维护一个可达和的集合。从 {0} 开始。对于每个数字，将它加到当前集合中的每个和上：reachable = reachable | {s + num for s in reachable}。进行筛选，只保留不超过 target 的和。最后检查集合中是否包含 target。这种方法直观易懂，但可能占用更多内存，实际运行速度也可能更慢。
def canPartition_set(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
reachable = {0}
for num in nums:
reachable = {s + num for s in reachable if s + num <= target} | reachable
return target in reachable
print(canPartition_set([1, 5, 11, 5])) # True复杂度分析
DP 方法的时间复杂度为 O(n × S)，其中 S = sum(nums)，并使用 O(S) 的空间存储布尔数组。对于 LeetCode 中的约束（n ≤ 200，sum ≤ 20,000），最多需要执行 4,000,000 次操作，速度非常快。集合方法具有相同的渐进复杂度，但由于构造集合的额外开销，实际运行速度可能更慢。
推广：统计和为某值的子集数量
还有一个相关问题：统计和为某个目标值的子集数量。将 DP 从布尔值改为整数：dp[c] = number of ways to reach sum c。使用加法代替 OR：dp[c] += dp[c - num]。将 dp[0] = 1 初始化。仍然使用反向遍历。这个推广展示了如何调整背包模板，以回答不同的子集相关问题。
def count_subsets(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for num in nums:
for c in range(target, num - 1, -1):
dp[c] += dp[c - num]
return dp[target]
print(count_subsets([1, 1, 1, 1, 1], 3)) # 10 (C(5,3))常见面试追问
请准备好回答以下追问：(1) 如果需要返回实际的划分结果，该怎么办？——需要使用二维 DP 进行重建。(2) 如果元素可以为负数，该怎么办？——可以平移目标值，或者使用字典代替数组。(3) 时间复杂度是多少？——O(n × sum)。(4) 如果许多数字相同，能否改进？——可以使用频次统计，减少外层遍历次数。请始终主动说明这些权衡。
与 0/1 背包的联系
Partition Equal Subset Sum 是 0/1 背包的直接应用：物品是这些数字，权重等于价值，背包容量等于 target。我们要判断最大价值是否等于 target（可行性），而不是求最大价值是多少。反向遍历方式完全相同，只有操作从 max 改为布尔运算 or。在面试中识别出这种联系，能够体现出较强的模式识别能力。
边界情况
需要处理的边界情况包括：(1) 长度为 1 的数组——单个元素无法拆分，因此始终为 False；(2) 所有元素相同且元素数量为偶数——是否可行取决于元素的具体值；(3) 总和非常大——分配 DP 数组前请先检查约束；(4) 大于 target 的元素——可以跳过，因为它们不可能属于和为 target 的子集。使用最大元素检查作为提前退出条件，可以高效处理情况 (4)。
快速检查
请检验您对本课程中“数据结构与算法——编程面试准备”相关概念的理解。
课程回顾
在本课中，您学到了：Partition Equal Subset Sum 可归约为目标值为 total//2 的子集和问题，布尔型一维 DP dp[c] 使用与 0/1 背包相同的反向遍历，以及将布尔 OR 替换为整数加法后，该方法可以推广到统计子集数量。接下来我们将学习目标和，把符号分配问题转换为关于子集和差值的背包问题。
常见问题解答
「等和子集分割」课时是免费的吗？
是的 — 「等和子集分割」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「等和子集分割」这节课中我会学到什么？
将分割问题重新表述为目标值为总和一半的 0/1 背包问题，并使用布尔 DP 数组判断是否可行。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「等和子集分割」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。