算法面试必考：分割等和子集的四大变种与解法套路

如果你刷过一阵子算法题，分割等和子集这个词大概率不陌生——给定一个非空数组，问能不能把它分成两个和相等的子集。经典解法是0/1背包：先算总和，如果总和是偶数，就把“选取若干元素凑出总和一半”的问题交给DP，一维数组倒着滚一遍就出结果。但我在实际刷题和帮人改代码的过程中发现，真正让人头疼的从来不是这个标准形，而是它的各种变种——从两堆变k堆、从判断可行性变成输出具体分组、从纯正整数变成带负数、从n=20变成n=10000。这些变种看起来都像“老朋友”，动起手来却一个比一个狡猾。

这篇文章就围绕“分割等和子集变种”这条线，把我自己推过的解法、翻过的车、总结出的套路完整梳理一遍。适合正在准备算法面试的人，也适合做竞赛题时一碰到“划分/等和/子集凑数”就发怵的同学。

1. 先厘清“等和分割”的底层逻辑：为什么本质是背包问题

1.1 经典题目的核心结论

先把最朴素的版本说清楚。输入一个非空正整数数组nums，判断能不能把整个数组拆成两个子集，使得两个子集的元素和相等。比如说[1,5,11,5]，答案是True，因为可以分成[1,5,5]和[11]。

分析路径是这样的：

• 两个子集和相等，意味着每个子集的和都是target = sum(nums) / 2。
• 如果sum(nums)是奇数，直接返回False，不用做任何DP。
• 问题就转成了：在nums里选出一组元素，元素和恰好等于target。这不就是0/1背包——每个物品选或是不选，容量就是target。

用一维布尔数组dp，dp[j]表示“能不能凑出和j”。初始化dp[0] = True。遍历每个num，内部从target倒着循环到num，执行dp[j] = dp[j] or dp[j - num]。倒序的原因很关键：保证每个元素只被用一次，不然就退化成了完全背包。

def can_partition(nums): total = sum(nums) if total % 2 != 0: return False target = total // 2 dp = [False] * (target + 1) dp[0] = True for num in nums: if num > target: return False for j in range(target, num - 1, -1): if dp[j - num]: dp[j] = True if dp[target]: return True return dp[target]

1.2 一维DP的细节与易错点

上面这段代码看起来简单，实际动手时至少有三个地方值得注意。

第一个是if dp[j - num]:这个提前判断。有些人习惯写成dp[j] = dp[j] or dp[j - num]，也没有问题，但内部循环里一旦当前dp[j]已经被更新成True，对后续j的计算不会产生副作用，因为dp[j - num]是更小的下标，本轮还没被当前元素污染。这一点和二维DP的“本轮更新不影响本轮后续判断”是同一个道理。

第二个是num > target的提前返回。如果数组里已经有一个数单独超过了target，那它无论如何也没法和另一半匹配，直接判负。这个小剪枝在经典题里可有可无，但放到变种题里经常是救命稻草。

第三个是我见过很多新手翻车的点：如果把一维DP理解成“从nums中任意选元素凑target”，就会忘掉dp[0] = True这个地基。没有它，后面全盘皆输，而且这个错误在样例数据小的时候特别隐蔽，因为[1,1]这种数据即使漏了初始化也可能碰巧通过。

从这三点就能看出来，所谓“经典题秒杀”只是面子，真正能不能写对，取决于你对0/1背包状态定义和更新顺序的理解够不够瓷实。

2. 从“两堆”到“k堆”：分割等和子集是如何演变成k-分割问题的

2.1 变种出现的必然路径

面试官和竞赛题不会满足于两堆。题目稍微改一笔：“给定数组nums和正整数k，判断能否把数组分成k个和相等的非空子集”，这就是分割等和子集最著名的变种，力扣原题编号698，也叫“划分为k个相等的子集”。

为什么这个变种是必然出现的？因为经典题本质是k=2的特例。面试官想考察的是你能不能把“两堆”的经验抽象成“多堆”，能不能从“选与不选”的0/1背包思维跳出来。

要对齐目标值：target = sum(nums) / k。注意，这里必须满足sum(nums) % k == 0，同时每个元素都不能大于target。

但接下来就不能无脑套背包了。原因在于：k堆需要同时跟踪“每一堆当前已经装了多少和”，这没法用一个简单的布尔数组表达。k=2时，你只要保证一堆是target，另一堆自动也是target；k大时，堆与堆之间的装填顺序和元素分配会互相影响。

2.2 状态压缩DP：用位运算记录“哪些元素被用过”

一个精确的做法是状态压缩DP。因为数组长度n通常不会太大（原题n <= 16），可以用一个n位的二进制掩码mask表示哪些元素已经被分到了某个子集里。目标状态是mask = (1 << n) - 1，表示所有元素都用完了。

常见的状态定义是：dp[mask] = 当前已经装好的组总和的“余数”，这个余数是当前正在装的这一组已经使用的元素和 % target。如果dp[mask] == 0，说明现在刚好装完若干组，可以开始装新的一组。

转移的时候，枚举一个还没用过的元素i，如果dp[mask] + nums[i] <= target，就把它放进去，更新dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target。这里为了减少状态数，还可以做一个小优化：状态初始化为-1，只对有效的mask继续转移，同时用记忆化或者BFS式的递推。

def can_partition_k(nums, k): total = sum(nums) if total % k != 0: return False target = total // k n = len(nums) nums.sort(reverse=True) if nums[0] > target: return False dp = [-1] * (1 << n) dp[0] = 0 for mask in range(1 << n): if dp[mask] == -1: continue for i in range(n): if mask & (1 << i): continue new_mask = mask | (1 << i) if dp[mask] + nums[i] <= target: dp[new_mask] = (dp[mask] + nums[i]) % target if dp[new_mask] == 0 and new_mask == (1 << n) - 1: return True return dp[(1 << n) - 1] == 0

这段代码的核心思路是：让dp[mask]记下“为了将来能凑完整组，当前这组还剩多少容量没用掉”，这是典型的余量状态法。很多人在这一步会想着直接记“哪些组已经满了”，结果状态爆炸。你真正需要在状态里保存的，只有“当前这一组已经装到哪了”。

2.3 回溯+剪枝：实际竞赛中更常用的方案

状态压缩DP看起来很标准，但实际竞赛和面试里，大部分人更愿意用回溯加剪枝，因为写起来快，而且对小数据剪枝效果惊人。

思路很简单：先用target确定每一组的目标和，然后从大到小排序，逐个元素尝试放入某个组。深度优先搜索时维护一个数组buckets，buckets[i]表示第i组当前的和。每放入一个元素就更新对应bucket，如果某个bucket等于target就继续下一个bucket。

剪枝有四个层次，我按实际效果从高到低排：

1. 从大到小排序。大元素先分配，能把搜索树压扁很多。
2. 同值去重：如果当前元素nums[i]和前一个元素nums[i-1]值相等，且nums[i-1]刚刚因为放不进当前桶而被剪掉，那么nums[i]也不用再试了。
3. 空桶剪枝：如果某个桶现在还是0，尝试把元素放进去失败后，直接跳过后续所有值为0的空桶，否则会重复尝试一模一样的失败路径。
4. 最小组剪枝：如果buckets中最大值已经超过target，立即终止当前分支。

def can_partition_k_backtrack(nums, k): total = sum(nums) if total % k != 0: return False target = total // k nums.sort(reverse=True) if nums[0] > target: return False buckets = [0] * k n = len(nums) def dfs(idx): if idx == n: return all(b == target for b in buckets) used_val = nums[idx] for b in range(k): if buckets[b] + used_val > target: continue # 同值去重 if b > 0 and buckets[b] == buckets[b - 1]: continue buckets[b] += used_val if dfs(idx + 1): return True buckets[b] -= used_val # 空桶剪枝 if buckets[b] == 0: return False return False return dfs(0)

这里buckets[b] == buckets[b - 1]的判定技巧值得多说一句：当两个桶当前的和相等时，把新元素放进它们中的任何一个，形态上是完全对称的。只尝试第一个，能一次性砍掉大量重复搜索。

对于n <= 16的数据，这个回溯法基本是瞬时出结果。但如果n到20以上，且k也偏大，回溯就会明显变慢，此时状态压缩DP才是更稳的选择。

3. “只需判断”与“输出方案”之间隔着一整个调试夜

3.1 为什么DP判断题变成构造题就难了

经典题和大部分变种只要求返回True/False，这掩盖了很多细节。可一旦加一句“请你输出一种划分方案”，整个问题的难度立刻上了一个台阶。

原因在于：一维DP只记录了“能不能凑出某个和”，它把所有“如何凑出”的路径信息都丢掉了。当你需要具体分组时，一维DP根本无从下手。此时必须回退到二维DP，或者干脆放弃DP，直接用回溯把所有方案搜出来。

3.2 具体操作：二维DP + 路径恢复

先把二维DP的转移公式写出来：

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

其中dp[i][j]表示用前i个元素能否凑出和j。注意这里的i是从1开始计数的，nums[i-1]对应第i个元素。

为了恢复路径，我要在DP过程中额外记录pre[i][j]：“dp[i][j]这个状态是从哪个状态转移过来的”。具体来说，如果dp[i-1][j]为True，说明不取第i个元素；如果dp[i-1][j-nums[i]]为True，说明取了第i个元素。恢复时从dp[n][target]倒推，每往前回退一个i，判断当前j是不是从j - nums[i]变过来的，如果是，就把第i个元素放进第一个子集。

def partition_with_solution(nums): total = sum(nums) if total % 2 != 0: return None target = total // 2 n = len(nums) dp = [[False] * (target + 1) for _ in range(n + 1)] dp[0][0] = True for i in range(1, n + 1): val = nums[i - 1] dp[i][0] = True for j in range(1, target + 1): if dp[i - 1][j]: dp[i][j] = True elif j >= val and dp[i - 1][j - val]: dp[i][j] = True if not dp[n][target]: return None subset1 = [] j = target for i in range(n, 0, -1): val = nums[i - 1] if j >= val and dp[i - 1][j - val] and not dp[i - 1][j]: subset1.append(val) j -= val return subset1, [x for x in nums if x not in subset1]

这里有个容易踩的坑：判断元素是否被选时，不能只看dp[i-1][j-val]是否为True，还要看dp[i-1][j]是否为False。因为如果两个方向都可能，你要优先认定“不选”，否则会选出一堆元素，最后根本凑不够target。这种行为在存在重复数值时尤其容易发生——明明dp[i-1][j]和dp[i-1][j-val]都为True，你却默认选了这个值，导致后续倒推错乱。

3.3 用回溯直接找方案时的去重策略

如果你不想写二维DP，回溯也是一种选择。回溯找方案的坑不在正确性，而在效率和无脑输出的重复组合。

比如数组[1, 2, 3, 6]，第一个子集可以是[1, 2, 3]或[6]。如果不做任何去重，递归树会同时走出“先选中1再选中2再选中3”和“先选中3再选中2再选中1”这种等价路径。经典的去重方法是：同一层递归中，跳过和前一个相同数值且前一个没有被选中的元素。

def dfs(idx, cur_sum, path, visited): if cur_sum == target: return path[:] for i in range(idx, n): if visited[i]: continue if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]: continue if cur_sum + nums[i] > target: break visited[i] = True res = dfs(i + 1, cur_sum + nums[i], path + [nums[i]], visited) if res: return res visited[i] = False return None

配合nums.sort()，当前元素如果已经超过剩余的target - cur_sum，后面更大的元素也不可能放进去，可以直接break。

4. 最容易翻车的四个变种场景与对应解法

4.1 负数元素：不能单纯用背包

经典题默认全是正整数，变种题可不一定。一旦nums里出现负数，0/1背包的索引和状态定义就崩了。

先看一个简单思路：如果总和非零，我们要找的是某个子集的和等于target = total / 2。出现负数，意味着选的子集里正负数互相抵消。一个可行的做法是把整个数组每个元素都加上一个偏移量offset，比如offset = abs(min(nums))，把所有数变成非负的。这样“凑出和target”就变成了“凑出和target + offset * m”，其中m是所选元素个数。可是问题来了：每个元素都要加偏移，但你不知道最终选了多少个元素，target没法固定。

更优雅的做法是拆分成正负数两部分。设所有正数和为P，所有负数和绝对值为N，数组总和为total = P - N。两个子集和相等，即每个子集和为total / 2。此时问题可以转化为：在白集合（正数和负数的绝对值）里选出一部分，要求“正数和”等于“负数和 + total/2”之类的等价关系。实际操作中，我建议直接在原数组上做DP，用字典记录可达和，比如dp[j]表示“当前可达的和为j”，负数参与转移时，从j + num更新过去。索引不固定就用哈希表：

def can_partition_with_negatives(nums): total = sum(nums) if total % 2 != 0: return False target = total // 2 dp = {0} for num in nums: new = set() for s in dp: new.add(s) new.add(s + num) dp = new return target in dp

这个做法简单但复杂度高，dp集合大小可能指数膨胀。不过对于带负数的变种题，数据规模通常不大，能用就要感恩。

4.2 重复元素非常多时的组合爆炸

另一种常见变种是：nums里同一个值出现几十次，比如[5, 5, 5, ..., 5]。此时回溯法的“同值去重”虽然能减少对称重复，但本质上还是在做全排列式的搜索。

更合理的方案是把相同值的元素合并成一个数量维度。假设值v出现了c次，问题变成“每个值最多取c个，能否凑出目标”。这就是多重背包，可以用二进制拆分优化成0/1背包，也可以用计数DP直接转移。

对于分割问题，还有一个思路：既然每个值的数量已知，那么dp[j]不再存布尔值，而是存“在当前前缀元素条件下，凑出和j时，最后一个元素还能剩多少个”。代码框架如下：

def can_partition_with_counts(values, counts, target): dp = [-1] * (target + 1) dp[0] = 0 for v, c in zip(values, counts): for j in range(target + 1): if dp[j] >= 0: dp[j] = c elif j >= v and dp[j - v] > 0: dp[j] = dp[j - v] - 1 else: dp[j] = -1 return dp[target] >= 0

这种“余量计数”DP源自经典的多重背包可行性判断，比简单布尔DP少一层循环，处理重复元素多的场景非常省事。

4.3 数据规模大、target很大时的bitset优化

如果nums有几百个元素，target有几十万，普通布尔数组做一维DP的空间是O(target)，时间O(n * target)，在Python里很容易被卡到超时。此时Bitset是标准答案。

思路是把dp这个布尔数组压成一个整数，用它的第j位表示“能否凑出和j”。每次处理一个元素num，执行dp = dp | (dp << num)。本质上是把所有可达和整体左移num位，表示“加上这个数之后的新可达和”。

def can_partition_bitset(nums): total = sum(nums) if total % 2 != 0: return False target = total // 2 bits = 1 for num in nums: bits |= bits << num return (bits >> target) & 1 == 1

这里bits的第0位初始为1，表示和0可达。每次左移之后还要和原值取或，相当于“选或不选”两种情况的并集。最终检查第target位是否为1就行。这个写法既简洁又高效，在target不特别巨大的时候，比列表DP速度快很多倍。

4.4 要求两个子集大小接近/要求最小差值

还有一类变种不要求等和，而是要求“两个子集和的差的绝对值最小”。这种实际上是“子集和接近target”的变体。

做法是把目标从target = total / 2变成“找到最接近target的子集和”。沿用一维布尔DP，记录所有可达和，然后从target向下找第一个可达的和best，那么两个子集的差就是total - 2 * best。

如果想输出方案，做法和第3章一样，只是回溯终点的判定从“恰好等于target”变成“与target差最小”。在实际编码中，可以边DP边记录一个best和对应的best_mask，最后根据best_mask反查选中了哪些元素。

def min_partition_diff(nums): total = sum(nums) target = total // 2 bits = 1 # 如果需要恢复方案，需要记录每个可达和对应的mask reachable = {0: 0} for i, num in enumerate(nums): new_items = {} for s, mask in reachable.items(): ns = s + num if ns <= target and ns not in reachable: new_items[ns] = mask | (1 << i) reachable.update(new_items) best = max(reachable.keys()) return total - 2 * best

注意这里用ns not in reachable跳过已经存在的和，避免覆盖已有路径，否则恢复方案时会丢信息。

5. 实测对比：我在不同变种上踩过的坑和性能数据

5.1 测试设计与结果表

我用自己的机器跑了一组对比实验，数据都是随机生成的，版本是Python 3.11。每组测试重复5次取中位数时耗，单位是毫秒。

从表格里能直观看出几件事：

• 在经典场景下，bitset比普通列表DP快一倍以上，而且代码量少很多。
• 回溯+剪枝在小n下甚至比状态压缩DP更快，因为状态压缩DP要遍历全部1<<n个状态，而剪枝往往提前终止。
• 一旦需要输出方案，二维DP+倒推是必须的；回溯虽然也能输出，但数据一过20就明显吃力。

5.2 三个印象深刻的坑

第一个坑是“一维DP + 试图恢复方案”。我一开始偷懒，想着dp数组里存布尔值，等全部算完再倒推。结果发现一维DP根本没有记录“从哪个上一层状态转移过来”，倒推时只能瞎猜，最后给出的方案和target对不上。后来老老实实换二维DP，问题立刻就没了。

第二个坑是“回溯没排序导致剪枝失效”。有一道k=4的题，数据是[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]，我没排序直接写回溯，跑了快半分钟都没出来。加上nums.sort(reverse=True)之后瞬间出答案。降序排序能让大元素优先占坑，大幅减少后续分支。

第三个坑是“带负数时直接套经典DP”。第一次处理负数变种，我惯性写了dp = [False] * (target+1)，结果负数索引直接报错。后来才意识到，负数和正数同时存在时，完全不能用target当作固定容量，只能退回到哈希集合或者做正负拆分。别看这个坑低级，换个人写一样会踩。

6. 快速识别“变种题”的套路与通用解题框架

6.1 变种识别清单

我总结了几个高频的信号词，看到就能立刻往分割等和子集上靠：

• “是否可以划分成k个和相等的子集”：经典题的k泛化，优先回溯+剪枝，数据小也可用状态压缩DP。
• “是否存在一个子集的和等于XXX”：本质是0/1背包，能用bitset就用bitset。
• “两组和的差的绝对值最小”：找最接近total/2的可达和，带上方案恢复逻辑。
• “输出任意一种划分方法”：从第一秒就决定用二维DP+路径恢复，不要尝试一维DP。
• “数组包含负数”：警惕，直接切换到哈希集合DP或者正负拆分，不要套固定容量背包。
• “某个值出现特别多次”：有余量计数DP这条路走。
• “n可能到几百，target到几十万”：先想bitset，再想别的，普通列表DP大概率超内存。

6.2 通用四步框架

结合上面这些变种，我自己总结了一套四步破题法。

第一步，定目标。无论是k分割还是两分割，先算total，再算target = total / k。立刻检查total % k，不是整数直接返回False。顺手检查max(nums) > target，大于也直接判负。

第二步，看数据规模。这一步决定算法方向。n <= 20优先回溯+剪枝；n <= 30且只要判断可行性优先bitset；n更大但target不大，用普通一维DP；target也很大，还是bitset；出现负数或者要求输出方案，另走分支。

第三步，选状态。如果要输出方案，选二维DP或回溯；如果只要判断，一维DP/bitset足够；如果k大且n中等，状态压缩DP是保底方案；如果重复值多，余量计数DP更高效。

第四步，剪枝和恢复。回溯必须排序+同值去重+空桶剪枝；DP恢复方案必须用二维表+分情况倒推；bitset恢复方案要额外保存每个可达和对应的mask，不能只存一个整数。

这套框架谈不上新颖，但胜在实用。我在帮别人review代码时发现，大部分“变种题卡住”的人，不是不懂某个解法，而是没在第一步就把问题归类清楚。你只要能在3分钟内说出来“这是k分割，n=16，要输出方案，用回溯加两个剪枝”，这道题就已经赢了一半。

最后分享一个小技巧：刷这类题的时候，别急着写代码，先把目标和数据规模写在草稿纸上。分割等和子集的变种再怎么换皮，最终都要落到“选一组元素，让它的和在某种约束下等于某个目标值”，而约束的种类决定了你该用背包、回溯还是bitset。想明白这一点，变种就不再是变种，只是同一道题的四种写法。