折半相遇（meet in the middle）

一旦 n 超過三十出頭，搜尋 n 件物品全部 2^n 個子集合就無望了。折半相遇是個巧妙的技巧，常能把指數砍半：不是一次列舉整個空間，而是把物品切成兩半，各 n/2 件，分別列舉每一半的所有子集合，然後巧妙地把兩張清單合併起來找出一對匹配。你做兩次大小為 2^(n/2) 的可管理搜尋並把它們接起來，而不是一次大小為 2^n 的不可能搜尋。

用子集合加總把它講具體。你想要 n 個數字中某個子集合加總為目標 T。把數字切成兩半 L 與 R。把 L 的全部 2^(n/2) 個子集合和列成一張清單，把 R 的全部 2^(n/2) 個子集合和列成另一張。任一完整解會用 L 的某個子集合（和為 a）與 R 的某個子集合（和為 b），且 a + b = T。所以把 R 的和排序，對 L 清單中的每個和 a，在 R 清單中二分搜尋值 T - a；命中就表示你找到了兩半能合成 T。成本是建每張清單 2^(n/2)，加上排序與搜尋 2^(n/2) log(2^(n/2))，即約 O(2^(n/2) * n)——遠勝 2^n。對 n = 40，2^40 約 10^12，但 2^20 只約 10^6，這是「難解」與「瞬間」之差。

對「有兩個可合併半邊」的指數問題，折半相遇是首選升級：子集合加總、k-sum、找碰撞，以及某些背包與密碼學搜尋。但它的要求是真實的：你得能把問題切開，使解能分解成一個 L 部分與一個 R 部分並可彼此匹配（這裡，和單純相加），而且你要付出記憶體代價——儲存 2^(n/2) 個部分結果本身就是指數，只是指數減半了。它不會把問題變成多項式；它替指數開了平方根，而這往往正是把「無望」變成「可行」的那一記助力。