← 返回首頁

Meet in the Middle 折半搜尋

陣列分割

左半部 (Left Half)
右半部 (Right Half)

合併搜尋

匹配結果 (左子集和 + 右子集和 = 目標)

目標和：-
找到的組合數：0

複雜度比較

暴力搜尋

-
列舉 2^n 個子集

折半搜尋

-
列舉 2^(n/2) + 排序合併

加速比

-
倍數

演算法說明

Meet in the Middle 將陣列分成兩半，分別列舉所有子集的和，然後用排序 + 二分搜尋（或雙指針）合併結果。

時間複雜度從 O(2^n) 降低到 O(2^(n/2) * log(2^(n/2))) = O(n * 2^(n/2))。