Meet in the Middle 算法详解

Meet in the Middle（中间相遇法）是一种用于优化指数级暴力搜索的算法技巧，常用于解决子集和、背包变种、组合枚举等在常规暴力下时间复杂度过高的问题。

基本思想

将原问题拆分为两部分，分别对两部分进行穷举，再通过某种方式（如哈希表或排序+双指针）合并结果，从而将时间复杂度从 O(2^n) 降低到 O(2^{n/2})。

典型应用场景

• 子集和问题（Subset Sum）
• 0-1 背包问题（当物品数较少但容量极大时）
• 密码破解中的中间相遇攻击（MITM Attack）
• 编程竞赛中的高维状态压缩问题

简单示例（伪代码）

// 假设 n = 40，直接枚举 2^40 不可行
// 将数组分为 A[0..19] 和 B[20..39]

leftSums = 所有 A 的子集和
rightSums = 所有 B 的子集和

对 rightSums 排序

for each sum in leftSums:
    target = total_target - sum
    if binary_search(rightSums, target):
        return true
    

优势与局限

优势：显著降低时间复杂度，适用于“中等规模”（n ≈ 30~50）的组合问题。

局限：需要额外空间存储中间结果，空间复杂度为 O(2^{n/2})；仅适用于可拆分的问题结构。