分割等和子集
Partition Equal Subset Sum
本机进度仅保存在当前浏览器
题目描述
给你一个只包含正整数的非空数组 nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例：nums = [1, 5, 11, 5]，输出 true（[1, 5, 5] 与 [11]）。
解题思路
- 能否分割等和 = 能否从数组中选出子集使和恰为 sum / 2，这是 0-1 背包的可行性判定版。
- sum 为奇数直接不可行；dp[x] 表示能否用已处理元素凑出和 x。
- 转移为布尔 OR：dp[x] |= dp[x - c]；内层金额必须倒序遍历，保证每个元素只用一次。
参考实现
查看参考实现Python · 建议先自行作答
def canPartition(nums):
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = [True] + [False] * target
for c in nums:
# 0-1 背包：金额倒序防止重复选取
for x in range(target, c - 1, -1):
dp[x] = dp[x] or dp[x - c]
return dp[target]