Meet-in-the-Middle | Codeboy's Blog

范式

把分治的 (n) 个变量分为两半，各枚举 (2^{n/2}) 个部分状态，再做低成本兼容查询。Subset sum 中生成左右子集和集合 (L,R)，对每个 (x\in L) 查 (T-x\in R)。 [ O(2^{n/2}\operatorname{poly}(n)) ] 时间和通常同阶空间。

它不是递归分治后合并线性答案，而是显式保存指数状态。Schroeppel–Shamir 可用更复杂生成顺序把某些问题空间降到 $2^{n/4}$ 。

数列 ((3,5,8,11))、目标 16，分成 ((3,5)) 与 ((8,11))。左和为 ((0,3,5,8))，右和为 ((0,8,11,19))。对左和 5 查补值 11 命中，恢复子集 ({5,11})。列表项必须携带 bitmask，否则只能回答存在而不能重构方案。

排序双指针从最小左和与最大右和开始：和过大就向左移动右指针，过小就向右移动左指针。若求方案数，重复和要压成 ((value,multiplicity))，命中时乘两侧次数；简单去重会丢解。若只问存在，哈希 membership 已足够。

各半 (2^{n/2}) 个状态，生成和排序为 [ O(n2^{n/2}+2^{n/2}\log 2^{n/2}) =O(n2^{n/2}), ] 双指针扫描线性，空间为 (O(2^{n/2}))。哈希给期望查询，排序给确定性查询并支持计数。

Schroeppel–Shamir 把每半再次分组，按序惰性生成两两和，用优先队列把空间降到 (2^{n/4}) 量级。它需要维护每行下一项的生成不变量，不是把列表简单拆成四份就自动省空间。

若跨半兼容条件不能由短摘要判断，组合检查可能退回 (2^n) 的笛卡尔积；图路径中大量跨边相互作用便可能需要更丰富边界状态。整数和必须防溢出，否则补值查询会产生伪匹配。

(2^{n/2}) 仍是指数，(n=80) 已意味着约 (2^{40}) 个半状态。MITM 是精确指数算法的时间—空间折中，不是多项式算法。

参考资料

Horowitz, Sahni, “Computing Partitions with Applications to Knapsack,” JACM, 1974.
Schroeppel, Shamir, “A T=O(2^{n/2}), S=O(2^{n/4}) Algorithm,” SIAM J. Comput., 1981.