用回溯解子集合加總（subset-sum by backtracking）

給你一袋數字和一個目標，你想知道其中某些數字能不能恰好加總成目標。用硬幣 6、8、3 和目標 9，答案是可以（6 + 3）。這是子集合加總問題，最直接的攻法是回溯：一次走一個數字，對每個就「把它加進當前總和」或「跳過它」這個二元決定分岔。

這裡的狀態空間樹就是子集合樹：在第 i 個物品你分兩岔，而一個節點裝著「到目前為止已納入物品的當前總和」加上「下一個是哪個物品」。遞迴是這樣的，對當前總和為 s 的第 i 個物品：若 s 等於目標，成功；若物品用完了，此分支失敗；否則試「納入第 i 個」（以總和 s + value[i] 遞迴）並試「跳過它」（以總和 s 遞迴）。純粹這樣會走訪全部 2^n 個子集合。把它表述成回溯而非盲目列舉的全部理由，就是剪枝。若所有數字非負，你能兩種剪枝：一旦當前總和超過目標，再納入任何東西都無濟於事，停（超額剪枝）；若當前總和加上所有剩餘物品的總和仍低於目標，此分支永遠到不了，停（不及剪枝）。把物品排序能讓這些界更早生效。

子集合加總之所以重要，一是它是通往 NP 完全的門戶（它是 NP 完全的，是分割問題與 0/1 背包的近親），二是它是個乾淨的地方，讓你感受剪枝如何改變一切。最壞情況下回溯仍是 O(2^n)——例如所有物品為零而目標也為零，每個子集合都是解，兩種剪枝都不會生效，於是你得走訪全部 2^n 個。但在許多真實實例上那兩個界把樹砍掉，而對中等 n，另一個點子折半相遇把指數降到約 2^(n/2)，相對於樸素的 2^n 是巨大的實際勝利。