當問題太大塞不進暴力，試著把它對半折——兩半分別暴力，中間相遇。
什麼情況適用？
暴力搜尋是 O(2ⁿ)，n ≤ 25 勉強可以接受，n ≤ 40 已經是 10^12 完全不行。
但如果問題有「前後兩半可以獨立枚舉，再組合比較」的結構，就可以折半：
n=40 的暴力：2^40 ≈ 10^12 次操作
折半後：各 2^20 ≈ 10^6 次，合併 O(2^20 × 20)
總計：~2000 萬次，遠低於 10^12子集和問題
給 40 個整數，是否存在子集的和恰好等於 target？
boolean subsetSum(int[] arr, long target) {
int n = arr.length, half = n / 2;
// 枚舉左半所有子集的和
List<Long> leftSums = enumerateSubsetSums(Arrays.copyOf(arr, half));
// 枚舉右半所有子集的和
List<Long> rightSums = enumerateSubsetSums(Arrays.copyOfRange(arr, half, n));
Collections.sort(rightSums);
for (long ls : leftSums) {
long need = target - ls;
// 二分搜尋 need 是否在右半的子集和裡
if (Collections.binarySearch(rightSums, need) >= 0)
return true;
}
return false;
}若要找「最接近 target 的子集和」，用雙指標：左半升序、右半降序，兩個指標向中間逼近，每步更新最佳答案。
背包問題變種
同樣的 40 個物品的 0/1 背包，直接 DP 是 O(nW)，若 W 很大（如 10^18）就失效了。折半後兩半各 O(2^20) 枚舉，再配合排序合併，總 O(2^(n/2) × n)。
雙向 BFS：同樣的折半思想
雙向 BFS 從起點和終點同時出發，在中間相遇：
單向 BFS：O(b^d)，b = 分支因子，d = 深度
雙向 BFS：O(b^(d/2))
b=10, d=10：
單向：10^10 = 100 億
雙向：10^5 = 10 萬Google 地圖的最短路徑搜尋、拼圖（八數碼）的最短解法，都用雙向 BFS。
使用前提
Meet in the Middle 能用，需要問題滿足：
- 答案由「前半決策」和「後半決策」組合而成
- 兩半可以獨立枚舉
- 組合的方式明確（和、XOR、或某個條件）
折半到底省多少
| 暴力 | Meet in the Middle | |
|---|---|---|
| 時間 | O(2ⁿ) | O(2^(n/2) × n) |
| 空間 | O(1) | O(2^(n/2)) |
| 撐得住的 n | ≤ 25 | ≤ 40 |
省時間是拿空間換的——你得把半邊的所有子集和存下來排序，這就是那個 O(2^(n/2)) 空間的來源。所以折半的甜蜜區是 n 在 30~40 之間：暴力已經跑不動，但 2^20 這張表還塞得進記憶體。再大就得換別的招了。
🎬 互動視覺化：折半搜尋動手玩 — 看左右兩半各自枚舉子集和、再二分對接的「中間相遇」，指數砍半的威力用動畫看最直接。
折半搜尋不是魔法，是結構性的洞察——當問題能被切成兩半獨立處理，計算量就從指數變成指數的一半次方。
接下來往哪走
- 掃描線：把二維問題拆成一維問題的連續處理 — 下一篇：另一種「換個切法問題就變簡單」的結構性技巧
- Backtracking 回溯法 — 折半之前的那條路：剪枝過的指數搜尋
- Bit Manipulation 位元運算 — 枚舉半邊子集用的 bitmask 技巧在這裡