子集和問題（subset-sum）

給你一堆標了號的硬幣與一個目標金額，你要回答：我能否挑「某些」硬幣（任一子集）恰好加總成目標？這就是子集和問題。它是數字裝填問題中最純粹的一個，也是通往 PARTITION（把數字分成兩個和相等的半）與 KNAPSACK（在重量上限下裝最多價值）的門戶。

形式上，子集和接收一組正整數 S 與一個目標 t，問 S 是否有某個子集恰好加總成 t。它屬於 NP：子集本身就是證書，驗證器只要把它的元素加起來與 t 比較，耗時多項式。PARTITION 是其特例，問 S 能否被分成兩個和相等的部分，相當於目標為總和一半的子集和。兩者都是 NP 完全，可由從 3-SAT 出發的歸約抵達，其中精心挑選的大數編碼了邏輯選擇，使得目標被恰好命中，當且僅當存在一個滿足子句的賦值。

子集和帶著一個著名而有啟發性的微妙之處，關乎「多項式」是什麼意思。有一個動態規劃演算法，執行時間正比於 n 乘以 t（物品數乘以目標）。它看似多項式，卻不是「輸入大小」的多項式，因為 t 以二進位只用約 log t 個位元寫成，所以 n 乘以 t 是位元數的指數量級。這樣的演算法稱為偽多項式：數字小時快，數字大時呈指數。因此子集和在與大數相關的強意義下是 NP 完全，這是「輸入大小」指的是位元數而非數值大小的教科書教訓。