4月10号刷题群里有人扔来一道经典题原名 Partition Equal Subset Sum翻译过来正好是“集合划分成两个和相等的子集”。题目描述就一句话给定一个只包含正整数的非空数组问能不能把它拆成两个子集让两个子集的和相等。我第一反应是DFS一个递归进去遇到 n30 的用例直接卡死后来才发现这题的难点根本不在搜索而在于把“划分两个集合”抽象成“找一个固定和的子集”再用状态压缩把指数级的东西压成位运算。这篇主要写给正在刷分割等和子集、或者之后打算碰“划分成 k 个等和子集”的读者下面是我完整重做一遍后的思路和踩坑记录。1. 把“划分两个集合”翻译成“找一个子集”1.1 为什么只需要找一半设整个数组的总和为 S。如果存在两个子集 A 和 B满足 sum(A) sum(B)那么一定有sum(A) S / 2sum(B) S / 2因为 A 和 B 互不重叠且正好覆盖全部元素A 的和一旦等于 S/2B 作为补集它的和自然也是 S/2。反过来也成立只要我能从数组里选出若干个数让它们的和恰好等于 S/2那么剩下没选的那些数它们的和也必然是 S/2。于是问题从“划分成两个集合”这种二元约束被等价成一个更简单的问题——“从数组中找一个子集使得子集和等于 target S/2”。这个等价关系是整个题目的第一块基石。很多刚开始刷这题的人想不通为什么它能套背包其实就是因为这一步消元你不必同时照顾两堆只需要关心“选不选某些元素来凑 target”。一旦找到了 target答案就是 true。1.2 奇偶性最便宜的一刀target S / 2 必须是整数所以 S 如果是奇数直接返回 false。这行判断不是优化是必要不充分条件的剪枝。做完奇偶性判断以后后面所有 DP 都只需要处理 target不需要再关心 S - target 那半边空间和时间都能省一半。我见过不少人写完 DP 才想起没判断奇数结果 target 是小数拿 int 一存直接出错。这个坑很小但在面试里特别容易因为紧张而漏掉。1.3 朴素DFS为什么会在大数据上崩盘最直觉的写法是 DFS每个元素要么分到第一堆要么分到第二堆递归树的大小是 2^n。n 20约 100 万次勉强能跑n 30约 10 亿次常规 OJ 一秒内绝对跑不完n 40约 1 万亿次想都不要想。即使你加上排序剪枝、当前和超过 target 就回溯最坏情况依然是指数级。而且 DFS 在这里有个隐性浪费路径不同但状态相同的情况大量存在比如前面选了 [1, 2] 和 [3] 可能到达同一个“当前用到哪几个元素”的状态纯递归不会复用这些中间结果。所以核心矛盾是子集数量本身就是 2^n如果不压缩枚举过程任何不带记忆化的搜索都救不了。顺着这个矛盾自然会引出两个方向——把指数级降半维的 meet in the middle以及用位集把“所有可达和”并行推进的状压 DP。2. 枚举子集与 meet in the middle从指数级到半指数级2.1 用二进制掩码表示一个子集先说什么叫状态压缩。假设数组长度为 n我用一个 n 位二进制数 mask 表示“选了哪些元素”第 i 位是 1表示 nums[i] 被选进子集第 i 位是 0表示没选。于是枚举所有 mask从 0 到 (1 n) - 1就是在枚举所有子集。写一个最简单的子集和枚举def subset_sums(nums): n len(nums) res [] for mask in range(1 n): s 0 for i in range(n): if (mask i) 1: s nums[i] res.append(s) return res这个写法很朴素但它把“集合”变成了“整数”这是后面所有优化的大前提。2.2 枚举子集的复杂度账要心里有数n 20 时2^20 1,048,576内层再乘 20大约 2000 万次运算能接受。n 30 时2^30 * 30 已经到 300 亿次单机跑不动。所以“直接枚举子集”只在小数据上成立超过 25 左右就必须换思路。这里的换思路不是放弃枚举而是把一枚举拆成两段枚举也就是 meet in the middle——看名字你可能觉得玄乎其实就是把数组分成两半分别枚举两半的所有子集和再把结果“撮合”起来。2.3 把数组劈成两半用哈希表撮合核心逻辑是如果存在一个完整子集的和为 target那么必然存在一个左半子集和一个右半子集它们各自的和加起来等于 target。换句话说对于右半的某个子集和 s只要 target - s 在左半的所有子集和里出现过答案就是 true。def can_partition_mim(nums): total sum(nums) if total 1: return False target total 1 mid len(nums) // 2 left, right nums[:mid], nums[mid:] def all_sums(a): sums set() m len(a) for mask in range(1 m): s 0 for i in range(m): if (mask i) 1: s a[i] sums.add(s) return sums left_sums all_sums(left) right_sums all_sums(right) for s in right_sums: if target - s in left_sums: return True return False复杂度从 O(2^n) 变成 O(n/2 * 2^(n/2))。n 到 40 时每一半 2^20 大约 100 万总共 2000 万级别轻松跑完。这个思路在“划分成两个和相等的子集”上不如 bitset 短但它的适用范围宽得多——负数、大数、带小数都能处理因为根本不需要连续 DP。2.4 两个容易忽略的细节第一空子集要算进去。左半的 subset_sums 天然包含空集的和 0所以右半如果自己就能凑出 target查 target - 0 时一定会命中逻辑不自洽的情况不会出现。第二左右两半怎么分不重要。奇数长度时多一个少一个都行但如果元素里有大量重复meet in the middle 会因为 set 去重反而跑得更快。实测中我习惯把数组先排一下序再切一半这样至少每半内部的枚举是确定的方便调试和肉眼验状态。3. 位集状压DP一行转移干掉整个内层循环3.1 先回到一维背包递推对于正整数、target 有限的情况这道题的经典解法是 0/1 背包。设 dp[j] 表示“能否用某些数凑出和 j”初始 dp[0] true然后对每个数 v从后往前更新vectorbool dp(target 1, false); dp[0] true; for (int v : nums) { for (int j target; j v; --j) { if (dp[j - v]) dp[j] true; } } return dp[target];为什么必须倒序因为正序更新时dp[j - v] 可能已经被本轮刚更新的 dp[j - v - v] 影响过于是同一个 v 会被重复使用这在 0/1 背包里是错的。倒序从高到低扫dp[j - v] 永远还是上一轮的状态每个元素只贡献一次。这段逻辑本身没问题但内层循环是 O(target)如果 n 是 200、target 是 100002,000,000 次操作还能接受如果 target 到百万级事情就开始棘手了。3.2 bitset把“一堆位置”当成一整条纸带位集优化的看法是不用一个个位置手动扫把 dp 看成一整条纸带第 j 位是 1 表示“和 j 可达”。新来一个数 v 时只需要把整条纸带往右推 v 格再和原来的纸带做一次按位或就完成了“每个已有和都尝试加上 v”的全部判断。bitset10001 dp; dp[0] 1; for (int v : nums) { dp | dp v; if (dp[target]) return true; // 提前终止 } return dp[target];这段代码的直观理解可以这样原来的纸带记录着所有你已能凑出的和dp v 相当于把纸带整体平移 v 个位置平移到的新位置代表“旧和 v”再和原纸带或起来相当于把“不选 v”和“选 v”两种结果合并。一次移位 一次按位或完成了原来一整层循环的事。3.3 为什么位集版本不需要倒序这是最反直觉但最关键的一点。在 dp | dp v 里赋值符号右侧会先求值右侧的 dp 是上一轮的完整状态因此 dp v 基于旧状态生成不会受到本轮更新污染。换句话说位运算天然就是“批量并行、快照式”的更新不存在数组循环里那种正序导致当前元素被重复使用的问题。我第一次写的时候还专门把 dp v 之后又原样左移了一次验了半天才发现自己多此一举。记住dp | dp v 就是完整的 0/1 背包一轮转移不需要额外套循环。3.4 Python 里的 int 位集也很能打很多 Python 玩家以为位集只能 C 玩其实 Python 的整数本身就是任意精度位集直接把 dp 当整数来移位def can_partition_bitset(nums): total sum(nums) if total 1: return False target total 1 dp 1 # 二进制第0位为1表示和为0可达 for v in nums: dp | dp v if (dp target) 1: return True return (dp target) 1 1性能上虽然不如 C bitset 快但胜在不用考虑容量上限target 多大都能自动扩。刷题或写原型脚本时非常好用。3.5 位集容量怎么定C 里bitset10001的 10001 是从哪来的题目限制了数组和的最大值所以 target 最大是总和一半这个上限保证 target 不会超过 10000。如果题目没有给总和上限就不要再用固定 bitset改用vectorbool配合大小计算或者直接用 Python int。更稳妥的做法是先算出total / 2判断它超过一定阈值时切到 meet in the middle。4. 从这题延伸出去的变形、误区和坑4.1 一个能让你直接WA的贪心我见过不少人一上来就说“从大到小排序轮流往两堆里放让两堆尽量平均”。这个思路在部分用例上是对的但不是普遍正确。反例[5, 5, 4, 3, 3]总和 20target 10。贪心“每次都放到当前和较小的一堆”5 放堆 AA5B05 放堆 BA5B54 放堆 AA9B53 放堆 BA9B83 放堆 BA9B11最后得到 9 和 11判定失败。但实际划分是 A{5,5}B{4,3,3}两边都是 10完全可行。原因是这个问题的本质是子集和不是调度均衡贪心只保证局部相差小不能保证局部决策不出现在全局上后悔的情况。4.2 划成 k 个等和子集时状态压缩的真正形态如果题目从“两个”变成“k 个”情况完全不同。比如 LeetCode 698“划分为 k 个相等的子集”target total / k答案要求是否存在 k 个互不重叠且全覆盖的子集。这时候 bitset 那种“只记录可达和”的模型不够用了因为我们不仅要判断“能否凑出 target”还得保证每个元素只用一次、并且所有元素都被用完。最常见的做法是用 mask 表示“哪些元素已经被放进某个桶”配合记忆化 DFSdef can_partition_k(nums, k): total sum(nums) if total % k: return False target total // k nums.sort(reverseTrue) if nums[0] target: return False n len(nums) full (1 n) - 1 from functools import lru_cache lru_cache(None) def dfs(mask, rem): if mask full: return True if rem 0: return dfs(mask, target) # 当前桶填满了开新桶 for i in range(n): if not (mask i) 1 and nums[i] rem: if dfs(mask | (1 i), rem - nums[i]): return True return False return dfs(0, target)这里的核心变化是状态从“可达和集合”变成了“已使用元素的掩码 当前桶剩余容量”。因为 k 个桶之间没有顺序差异所以状态量是 O(2^n * target)n 一般不超过 16 才比较稳。这个场景才是真正的“状压dp 枚举子集”枚举的是“下一个放哪个元素”记忆化的是“已经用过哪些元素”。4.3 有负数、有0、target很大的边界情况这道题通常限定正整数但实际工程里不一定。如果数字里出现负数bitset 的dp v遇到负数 v 就失效了因为负移位没有意义这时候建议退回到集合迭代用一个 set 保存所有可达和每来一个数 v把集合里每个已有和 s 变成 s v再并回原集合。复杂度是 O(n * 可达和的个数)虽然慢但至少正确。如果数组里有 0总和不改变但枚举子集时 0 会让 2^n 里的很多 mask 对应相同和。bitset 版本完全不受影响dp | dp 0等于没变安全meet in the middle 版本也安全因为 set 自动去重。如果 target 非常大比如总和达到百万千万开固定大小 bitset 会爆内存这时优先切 meet in the middle。这提醒我解法选择不是越高级越好而是要对着数据范围做取舍。4.4 需要输出具体划分方案时怎么改原题只问能否划分但面试官很可能追加一句“把方案输出一下”。常见做法是给 DP 加二维记录pre[i][j]表示在考虑前 i 个数时若和 j 可达是由哪个数转移来的找到 target 可达后从 dp[n][target] 往回倒推把命中路径上的数字放进子集 A其余放 B。如果用位集版本输出方案时会麻烦一些因为位集不保存转移来源。我的一般做法是题目只问能否时用位集题目要方案时退回二维 bool DP 配合 pre 数组。算法竞赛里时间紧没必要为输出方案做 fancy 优化。5. 读题时的决策顺序与我的实操经验5.1 看到“每个元素选或不选”先算决策空间这道题让我养成了一个习惯读题后第一时间不是写代码而是先把决策空间列出来。凡是“每个元素选或不选”的模型第一反应就是 2^n然后按 n 的规模分线数据规模推荐做法n ≤ 20直接枚举子集 / 记忆化DFSn ≤ 40meet in the middletarget 有限且都是正整数0/1 背包可上 bitsetn 很大但总和有限bitset 提前终止其他大 n 且元素非负优先 meet in the middle这个表不是死规则但它能避免我在 30 分钟里反复横跳。实际问题里我会先算 total 和 target再算 n 的上限最后决定走 meet in the middle 还是 bitset。5.2 bitset 带来的“并行思维”不止在这题有用位集背包的好处是把 O(n * target) 压成 O(n * target / 字长)本质是用硬件的位并行去换时间。这种“按位表示布尔集合用移位做整体平移”的思维在子集和问题、硬币找零问题、甚至某些区间覆盖问题里都能复用。比如判断“能不能从一堆数里凑出某个区间的所有和”或者“两个数字集合的和是否有交集”bitset 都是非常趁手的工具。它不一定是最快的但写起来最短、最难错。5.3 调试时的对拍和可视化套路刷这道题时我最依赖的是两件事一是写一个暴力枚举所有子集和的函数然后用随机数组和 DP 结果对拍。n 取 12 到 16随机生成几百组跑一遍能揪出绝大多数边界错误。二是可视化位集。C 里dp.to_string()可以直接打印每一位Python 里bin(dp)能从低位看到高位。我调试过一次“target 位判断写错”的问题就是靠打印bin(dp)肉眼比对我原以为某个位置应该是 1结果它离正确位置隔了一位一看就发现是右移位数搞错了。5.4 个人体会这道题我前前后后写了三版DFS、普通背包、bitset。真正理解位集那句dp | dp v之后再回头看 k 等和子集的问题思路会顺很多——前者压缩的是“和”后者压缩的是“元素集合”。如果你正打算练状态压缩这一题是非常好的起点别急着背模板自己拿纸笔画一遍“纸带平移”的过程比什么记忆都有效。