Meet in the Middle(中间相遇法)是一种用于优化指数级暴力搜索的算法技巧,常用于解决子集和、背包变种、组合枚举等在常规暴力下时间复杂度过高的问题。
将原问题拆分为两部分,分别对两部分进行穷举,再通过某种方式(如哈希表或排序+双指针)合并结果,从而将时间复杂度从 O(2^n) 降低到 O(2^{n/2})。
// 假设 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});仅适用于可拆分的问题结构。