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}$ 。

直觉

直接枚举全部组合要付 $2^n$ ；把变量分半后，任一完整解都可写成一个左状态与一个右状态的兼容配对。显式存下一侧的短摘要，就能用排序、双指针或哈希查补值，把笛卡尔积搜索换成两张约 $2^{n/2}$ 的表。

例子与边界

数列 $(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 是精确指数算法的时间—空间折中，不是多项式算法。

推论与应用

Meet-in-the-Middle 适合 subset sum、knapsack、密码分析和若干小规模精确搜索，核心条件是跨半兼容性可由紧凑状态快速判定。Schroeppel–Shamir 等方法还能以惰性生成降低空间，但仍保留指数时间与更复杂的生成顺序不变量。

参考资料

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.