Partition Equal Subset Sum
你会得到一个由正整数组成的数组 nums。判断你能否将这些值分成两组，使两组的和相等。每个值只能放入一组，且一组可以取自任意位置的值。如果存在这样的分组，则返回 true，否则返回 false。
函数
- numsinteger-array
- 要拆分成两组的正值
- 返回值boolean
- 当这些值可以分成两组且每组的总和相等时为 true，否则为 false
约束条件
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 100
示例
- 输入
- nums = [6, 1, 4, 9, 2]
- 输出
- true
- 解释
- 总数是 22，所以每组需要 11。9 + 2 和 6 + 1 + 4 两组的和都是 11，所以答案是
true。
- 输入
- nums = [4, 7, 2, 9, 6]
- 输出
- false
- 解释
- 总数是 28，所以每组需要 14。拥有 9 个的组还需要 5 个，而 4、7、2 和 6 无论怎么组合都凑不出 5，所以答案是
false，即使总数是偶数。
- 输入
- nums = [1, 2, 3, 5]
- 输出
- false
- 解释
- 总和是 11。两个相等的整数相加，结果总是偶数，所以奇数总和永远无法拆分，答案是
false。
进阶
无法平均分组时，你能返回两组总和之间可能的最小差值吗？
提示
逐个打开提示，每个都会多透露一点。
如果两组的和相等，那么每组的和必须是多少，用
nums的总和表示？总和是奇数又能立刻告诉你什么？你只需要找到一组数，使它们的和达到总和的一半；剩下的值就构成另一组。想一想前几个值能够得到哪些和，以及再加入一个值后，这些和会如何变化。
维护一个布尔数组
reach[0..target]，其中只有reach[0]为 true。对于每个值num，让s从target递减到num，当reach[s-num]已标记时，就标记reach[s]。从大到小遍历可以避免重复使用同一个值。
题解
每组的和都必须是总和的一半，因此问题就变成了：是否存在 nums 的某个子集，其和等于 target = total / 2？尝试所有子集需要 2^n 次操作。不过，和的范围较小，最大为 200 × 100 / 2 = 10^4，因此可以用记录可达和的 0/1 背包表，在 O(n × target) 步内得出答案。
用递归尝试每个子集
结果正确，但无法在最大的测试中运行完毕
思路
如果总和是奇数，就不存在拆分方法。否则，为第一组选择数值，直到它们的和达到 target；剩下的数值自然组成另一半。辅助函数 reach(i, remaining) 会依次决定是否选取每个数值：选取 nums[i]，或跳过它。
每个子集都对应一条选择路径，因此搜索不会漏掉任何拆分方法。对于无法拆分的输入，搜索几乎必须遍历所有路径，最多达到 2^n 条：当 n = 40 时约为 10^12 条，当 n = 200 时约为 1.6 × 10^60 条。
算法
- 将
nums中的值相加。如果总和是奇数，返回false。 - 将
target设为总和的一半。 - 编写
reach(i, remaining)：当remaining为 0 时返回 true；当i超过最后一个值，或remaining小于 0 时返回 false。 - 否则，返回
reach(i+1, remaining-nums[i])或reach(i+1, remaining)：选择这个值或跳过它。 - 返回
reach(0, target)。
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
# Can some of the values from index i on add up to exactly remaining?
def reach(i, remaining):
if remaining == 0:
return True
if i == len(nums) or remaining < 0:
return False
# Put nums[i] in the first group, or leave it for the second one
return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)
return reach(0, total // 2)按值填充表格并求和
思路
reach(i, remaining) 只取决于两个数字，因此最多有 (n+1) × (target+1) 个不同的问题，大约是 201 × 10001 ≈ 2 × 10^6。把每个问题的答案只计算一次，并存入表格：can[i][s] 表示前 i 个值中是否有一些值的和为 s。第 0 行全为假，只有 can[0][0] 除外。
值 num = nums[i-1] 要么不选，这样之前的值已经能凑出 s；要么选它，这样之前的值就需要凑出 s-num。每一行只读取上一行，因此每个值最多使用一次。在第一个示例中，可凑出的和从 {0} 增长到 {0, 6}，再到 {0, 1, 6, 7}，最后到 {0, 1, 4, 5, 6, 7, 10, 11}：6 + 1 + 4 可以凑出 11。
算法
- 如果总和是奇数，则返回
false，并将target设为总和的一半。 - 创建一个有 n+1 行、target+1 列的表，初始值全部为 false，并将
can[0][0]设为 true。 - 对于从 1 到 n 的每一行
i，取num = nums[i-1]。 - 对于从 0 到
target的每个和s，将can[i][s]设为can[i-1][s]；如果s ≥ num，则还要考虑can[i-1][s-num]。 - 返回
can[n][target]。
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
n = len(nums)
# can[i][s] is True when some of the first i values add up to s
can = [[False] * (target + 1) for _ in range(n + 1)]
can[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for s in range(target + 1):
# Leave num out, or put it in and reach s - num with the values before it
can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
return can[n][target]一行总和，从上到下填入
思路
每一行只读取上一行，所以保留一行 reach，并在原位置更新。更新顺序很重要。让 s 从小到大遍历时，会读取当前值已经标记为可达的和：在第一个例子中，1 会先标记和 1，然后读取它来标记 2，再标记 3，就好像你有很多个 1 一样。
让 s 从 target 向下遍历到 num。这样，s-num 是当前值尚未触及的索引，因此 reach[s-num] 仍等于 can[i-1][s-num]。一旦 reach[target] 为 true，就可以停止，因为后续的值不会移除任何和。时间复杂度仍为 O(n × target)，内存则减少到 target + 1 个布尔值。
算法
- 如果总和是奇数，则返回
false，并将target设为总和的一半。 - 创建一个包含
target + 1个条目的reach，除reach[0]外，其余条目都设为 false。 - 对于每个值
num，让s从target递减到num，当reach[s-num]为 true 时，将reach[s]设为 true。 - 处理完每个值后，如果
reach[target]为 true，则返回true。 - 如果循环结束，则返回
reach[target]，此时它为 false。
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
# reach[s] is True when some of the values seen so far add up to s
reach = [False] * (target + 1)
reach[0] = True
for num in nums:
# Walk the sums downward so num is used at most once
for s in range(target, num - 1, -1):
if reach[s - num]:
reach[s] = True
if reach[target]:
return True
return reach[target]
易错点和边界情况
- 在单行版本中从小到大遍历总和。对于
[3, 9]，目标值为 6，3 会标记总和 3，然后标记总和 6，于是你会回答 true。 - 漏掉奇数检查。对于
[1, 2]，总和 3 向下取整后，目标值为 1，值 1 可以达到它，于是你会回答 true。 - 每次都把值加到较轻的一组中。对于
[3, 3, 2, 2, 2]，最终两组的总和分别为 7 和 5，但实际上 3 + 3 = 2 + 2 + 2。 - 没有跳过大于目标值的数值，例如
[2, 2, 2, 10]。在 R 中，像(num+1):(target+1)这样的范围会倒序计数，从而中断循环。 - 在 Lua 或 R 中，从索引
s读取总和s，但它实际位于s + 1处。
常见问题3
为什么“分割等和子集”是一个 0/1 背包问题？
你要恰好装满容量为 target = total / 2 的背包，每个值最多使用一次。每个值只能选或不选，这是 0/1 选择，而且值的大小就是它本身。可达和表可以在 O(n × target) 时间内解决这个问题。
分割等和子集的时间复杂度是多少？
时间复杂度为 O(n × target)，其中 target 是总和的一半；使用一行时，空间复杂度为 O(target)：对于 200 个最大值为 100 的数，大约需要 2 × 10^6 步。这个上界会随数值大小增长，因此它是伪多项式的；一般问题是 NP 完全的。
能用位集解决“子集和等分”问题吗？
是的。将可达的和存储为一个大数的各个位，并将第 0 位设为 1。对于每个值，bits |= bits << num 会一次性将它加到每个可达的和上，答案就是第 target 位。这和同一张表的原理相同，只不过每个机器字包含 64 个和。
def canPartition(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [6, 1, 4, 9, 2]
预期输出
true