當聰明的剪枝也不夠用時
前三篇指南玩的都是同一個遊戲：保住暴力法的誠實，但拒絕去看那些不可能有意義的候選解。回溯法砍掉那些已經破壞規則的子樹，而分支定界法砍掉那些「最好的可能結果都贏不過手上答案」的子樹。但剪枝有一道天花板。在一個約束很少、沒什麼好利用的困難實例上，無論你的界有多銳利，搜尋空間都可能頑固地貼在 2^n 附近——根本沒有足夠多註定失敗的分支可砍。遇到這種情況，修剪這棵樹已經不是辦法了。你需要攻擊的是「指數」本身。
這個訣竅一句話就能說完，而且它和之前的一切是真正不同的：中間相遇法把 n 個決定切成兩半、每半 n/2 個，把每一半「各自獨立地」完整暴力展開，再把兩份部分結果的清單合併起來。每一半只有 2^(n/2) 個候選解、而不是 2^n 個，所以你做兩趟便宜的掃描，再付一筆不算貴的代價把它們接起來——而不是對全部東西做一趟毀滅性的掃描。整個收益來自一個事實：2^(n/2) + 2^(n/2) 比起 2^n 小得可笑：在 n = 40 時，那大約是一百萬加一百萬，對上一兆。
一個示範例：把子集和對半切
拿最乾淨的情形來看，也就是我們在子集和底下見過的那個：給定 n 個數字和一個目標 T，是否存在一個子集恰好加總為 T？樸素的暴力法會試遍全部 2^n 個子集（透過數位元遮罩來列舉子集）。現在把這些數字切成左半邊 L 與右半邊 R，每半 n/2 個。整體的任何一個子集，都是「一個左半部分」加上「一個右半部分」，而它的總和就是（左半部分之和）+（右半部分之和）。這個可加性就是樞紐：兩半互不干擾，所以我們可以一次只處理一半。
- 列舉左半邊 L 的全部 2^(n/2) 個子集，把它們的和存進一份清單 A。同樣地，把右半邊 R 的全部 2^(n/2) 個子集列舉進一份清單 B。
- 把 B 排序（或載入一個雜湊集合）。這是讓配對能跑得快的那一道準備工序。
- 對 A 裡的每一個和 a，問一句：B 裡有沒有值 T - a？如果左半部分貢獻了 a，我們就需要右半部分剛好貢獻剩下的部分。一次命中就代表 a +（T - a）= T——一個真正達到目標的整體子集。
- 在排序好的 B 上用二分搜尋查 T - a 要花 O(log(2^(n/2))) = O(n)，或者用雜湊集合平均 O(1)。對全部 2^(n/2) 個 a 都跑這個查找，你就得到答案了。
注意排序扮演的角色：它把第二半從「一份我們必須掃描的清單」變成「一個我們可以探詢的結構」。用二分搜尋去問「T - a 在不在？」，正是讓這次合併變便宜的那個訣竅；而中間相遇法倚靠一個排序好的半邊，並非偶然——搜尋一個排序好的集合，正是生成一個未排序集合的天然搭檔。
計算代價——以及它為什麼行得通
令 m = 2^(n/2) 為每一半清單的大小。生成 A 和 B 各花 O(m)。把 B 排序花 O(m log m)，這對 m 而言是線性對數時間。配對做了 m 次查找，每次 O(log m)，又是一個 O(m log m)。全部加起來，整個方法是 O(m log m) = O(2^(n/2) * n) 的時間。把它和樸素暴力法的 O(2^n) 比一比：指數被砍了一半。這就是全部的獎賞，寫成一行。
plain brute force: O(2^n)
meet in the middle: O(2^(n/2) * log(2^(n/2)))
= O(2^(n/2) * n)
n = 40: 2^40 ~ 1.1e12 vs 2^20 * 40 ~ 4.2e7
(about a trillion) (about 40 million)它為什麼正確？靠的還是我們整個階段都倚靠的那個「完全列舉」承諾，只是被切成了兩份。每一個完整子集，都是某個左半部分和某個右半部分的配對，而步驟 1 生成了「每一個」左半部分和「每一個」右半部分，所以每一種配對都搆得著。步驟 3 則針對每個左半部分，檢查它所需要的那個確切右半部分存不存在。沒有任何東西被漏掉，因為這個可加切分在兩邊都是窮盡的；也沒有任何重複計算會騙過一個「是／否」的問題。這個合併步驟，做的正是那「消失的另一半暴力掃描」原本要做的工作——只不過它是用查找來做，而不是用重新列舉。
它向你索取什麼——以及它在哪裡止步
這麼好的東西沒有白拿的，而這筆帳是用記憶體來付的。樸素暴力法可以只用 O(1) 的額外空間跑——生成一個候選解、測試它、然後丟掉。中間相遇法則必須「儲存」整整一半份量的部分結果，以便稍後查找：O(2^(n/2)) 的空間。這是一筆實實在在的交易，也是那個經典的「以空間換時間」買賣。在 n = 40 時，每份清單大約裝一百萬個項目，還算舒服；在 n = 60 時，它們大約裝十億個，那就是新的牆。中間相遇法把斷崖往後挪了，大致讓你能處理的 n 翻倍——但這道斷崖仍然是指數的，只是現在指數是 n/2。
還有一個容易忘記的前提：這兩半必須透過某種乾淨、「可搜尋」的關係來結合。子集和行得通，是因為部分和會相加，而「需要 T - a」是一次單一、確切的查找。0/1 背包的版本也類似行得通，不過在配對之前，你必須在每一半裡只保留那些「未被支配的」（重量、價值）配對。但如果兩半以一種糾纏的方式互動——每一個左邊的選擇都改變了每一個右邊選擇的意義——那就沒有乾淨的接合可以利用，這個方法也就不適用。中間相遇法是專家的工具：當決定能以可加的方式切分時它極為出色，當不能時它毫無用處。
它的定位，以及接下來往哪走
退一步，看看這整個階段的形狀。我們以誠實、盲目的生成與測試開場，接著學會讓生成器變聰明：剪掉不可行的分支、用界把沒希望的分支砍掉。中間相遇法則是那個古怪的表親——它根本不剪枝。取而代之，它從一個完全不同的家族借了一招，也就是你會在分治法階段正面研讀的那個「切分後再合併」的想法。差別在於：經典的分治法會對兩半都遞迴下去再合併；而這裡我們把每一半攤平地暴力展開，只合併一次。同樣的直覺（一個問題切成兩半，會比兩倍還容易），不同的檔位。
最後那個指路牌，正是走出這個階段的橋。這裡的一切都圍繞著「馴服窮舉搜尋」——靠著按順序列舉、剪掉註定失敗的、用界砍掉沒希望的，以及今天的「切分指數」，讓「把每件事都試一遍」變得能存活下來。接下來的幾個階段則徹底改變策略：它們不再聰明地搜尋所有候選解，而是藉由重複利用「彼此重疊的子問題」的答案，避免去建構出絕大多數候選解。請把一個教訓帶在身上勝過一切：搜尋空間永遠是該最先估大小的那個東西，因為正是它的大小，決定了你究竟可不可以列舉——以及若不可以，你又必須召喚出哪一種聰明才智。