Meet in the Middle：把 O(2ⁿ) 砍成 O(2^(n/2))

當問題太大塞不進暴力，試著把它對半折——兩半分別暴力，中間相遇。

什麼情況適用？

暴力搜尋是 O(2ⁿ)，n ≤ 20 勉強可以接受，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 能用，需要問題滿足：

1. 答案由「前半決策」和「後半決策」組合而成
2. 兩半可以獨立枚舉
3. 組合的方式明確（和、XOR、或某個條件）

---

折半搜尋不是魔法，是結構性的洞察——當問題能被切成兩半獨立處理，計算量就從指數變成指數的一半次方。