Meet-in-the-Middle

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

Subset Sum 全程执行 ​

数列 $(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 已足够。

成本和空间 ​

对 $n\ge 1$，两半列表的直接生成和比较排序合计为

双指针扫描线性，空间为 $O(2^{n/2})$ 个记录。这里假定所有部分和、掩码与列表地址可放入机器字，整数运算与比较为单位成本；否则另计表示和位运算成本。使用哈希时，固定输入独立于随机种子、负载受控且哈希求值为常数成本，才有相应的期望查询界；比较排序不需要这项随机假设。

Schroeppel–Shamir 把变量均分成四组，各自存储约 $2^{n/4}$ 个子集和。若第一、二组的排序列表为 $A,B$，对每个 $A_i$，该行 $A_i+B_0,A_i+B_1,\dots$ 已有序。最小优先队列理路优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。只保存每行尚未输出的首项；取出 $(i,j)$ 后放入 $(i,j+1)$，就能依次生成两组合并后的和，而不保存全部配对。另两组反向用最大优先队列生成降序和，再用两端匹配。列表与队列只占 $O(2^{n/4})$ 个记录，朴素二叉堆实现的总时间为 $O(n{2}^{n/2})$；这些界仍采用上述单字记录与算术假设。

失效边界 ​

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

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

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