「湊得出這個數嗎？」——最精瘦的 NP-Complete 問題，以及把 \(2^n\) 砍成 \(2^{n/2}\) 的漂亮技巧

難度定位

• 兩者都是 NP-Complete（Karp 21 問題成員；由 3-SAT 經 Exact Cover 歸約而來）。

• 和背包一樣是弱 NP-Hard：有 \(O(nT)\) 偽多項式 DP。數字小就好解，數字大（例如 40 個 13 位數）才露出獠牙。

• Partition 是「最容易被低估的 NP-Complete 問題」——敘述只有一句話，卻是排程、公平分配等問題難度的源頭（本系列第 12 篇 Job Scheduling 的難度正是從它來的）。

演算法一：偽多項式 DP

可達性表

\[reach[s] = \text{「用目前處理過的數字，能否湊出總和 } s \text{」}\]

初始 \(reach[0]=\) 真。每加入一個數 \(a_i\)，把所有可達的 \(s\) 推進到 \(s+a_i\)（一維陣列需由大到小掃，避免同一數字用兩次）。時間 \(O(nT)\)、空間 \(O(T)\)。

還原方案

把布林表升級成 \(from[s]\) =「\(s\) 第一次變可達時用的數字索引」。回溯時從 \(T\) 一路減回 0：

手算範例

\(A=\{3,34,4,12,5,2\}\)、\(T=9\)。依序處理，列出每步後的可達集合（只列 \(\leq 9\)）：

答案：YES，\(9 = 4+5\)。

演算法二：Meet-in-the-Middle

動機

若數字大到 \(10^{12}\)，\(O(nT)\) 的表根本開不出來。純枚舉 \(2^n\) 在 \(n=40\) 時是 \(10^{12}\) 也不行。MITM 的想法：把 \(n\) 個數切成兩半，各自枚舉，然後「在中間會合」。

做法

1. 左半 \(n/2\) 個數：枚舉全部 \(2^{n/2}\) 個子集和，存進清單 \(L\)。

2. 右半同理得 \(R\)，將 \(R\) 排序。

3. 對每個 \(\ell \in L\)，在 \(R\) 中二分搜尋 \(T-\ell\)。找到即 YES。

\[T(n) = O\!\bigl(2^{n/2}\cdot n\bigr) \qquad \text{（排序與搜尋的 log 因子併入 } n\text{）}\]

\(n=40\)：\(2^{40}\approx 10^{12}\) 變成 \(2^{20}\approx 10^{6}\)——平方根級的加速，代價是 \(O(2^{n/2})\) 記憶體。

延伸問題：最平衡分割

Partition 無解時，退而求其次：把 \(A\) 分成兩堆使差最小。做法：對 \(T=\lfloor \frac{\sum a_i}{2}\rfloor\) 建可達表，從 \(T\) 往下找第一個可達的 \(s\)，答案為 \(\sum a_i - 2s\)。這是排程（兩台機器最小化 makespan）的核心子程序。

完整 C++ 程式

包含：DP + 方案還原、MITM（含 long long 大值版本）、Partition、最平衡分割。編譯：

g++ -std=c++17 -O2 -Wall -Wextra -o subset_sum_partition subset_sum_partition.cpp

執行結果與解讀

=== Example 1: subset sum with reconstruction ===
target=9 -> YES  {4,5} (sum=9)
target=11 -> YES  {4,5,2} (sum=11)
target=30 -> no

=== Example 2: partition into two equal halves ===
{1,5,11,5}: YES  side A = {11} (sum=11)
{1,2,3,5}: no (odd total or unreachable)

=== Example 3: most balanced split (min difference) ===
{8,6,5,14,13,9,12,7} total=74 -> min diff = 0
{3,1,4,2,2,1} total=13 -> min diff = 1 (odd total, best split is 6/7)

=== Example 4: huge values -> meet-in-the-middle ===
n=36, values ~1e12, target reachable? YES  (65.8 ms, 2^18 = 262144 sums per half)
(DP would need an array of ~31040422420851 entries -> impossible; MITM wins)

實務應用

• 公平分配：遺產、合夥拆帳、雲端負載對半分——全是 Partition 的變形。

• 對帳與審計：「這批交易中哪幾筆加起來等於這個異常總額？」——會計舞弊偵測的常見子問題。

• 密碼學：背包密碼系統與格密碼的安全性分析都圍繞 Subset Sum 的難度；低密度實例可用 LLL 格基化簡攻破。

• 排程：兩台相同機器的工作分配 = 最平衡分割（見本系列第 12 篇）。

練習題

1. 手算：\(A=\{7,3,2,5,8\}\)、\(T=14\)，畫出可達集合的演化表並還原方案。

2. 把 DP 的可達表改用 std::bitset，用位移一次推進整排：reach |= reach << a[i]。實測比逐格快多少。

3. 計數版本：湊出 \(T\) 的方法數有幾種？（把布林改成計數，注意溢位。）

4. MITM 目前回報「可不可行」，把它升級成能還原「左右各選了哪些」。

5. 挑戰：3-Partition（分成三堆等和，每堆恰 3 個數）是強 NP-Complete——想想為什麼偽多項式 DP 救不了它。

小結

延伸閱讀：Horowitz & Sahni (1974) 首次提出 MITM 解 Subset Sum；Garey & Johnson Computers and Intractability 的 Partition 條目；Howgrave-Graham & Joux (2010) 更快的 \(O(2^{0.337n})\) 演算法。