題目目錄Target Sum

正負號問題轉成湊出 P 的子集合有幾種。

TIME O(n · P)空間 O(P)，P = (total + target) / 2

01 / 子集合計數 DPSUM

total—

target—

P—

x—

s—

nums 綠色：已放入考慮；橘色：目前的 x

dp dp[s] = 湊出總和 s 的方法數

正在更新的 dp[s]本輪已更新來源 dp[s − x]（仍是舊值）

目前操作—每次只執行高亮的程式碼

STEP 01

速度

02 / 同步程式碼PYTHON

原理說明：為什麼可以變成子集合問題？

把加號的數字放一組，減號的放另一組。

設正號組總和 P、負號組總和 N。P − N = target，P + N = total，相加得 P = (total + target) / 2。只要數「總和恰好為 P 的子集合」有幾個，就是答案。

P 必須是非負整數：|target| > total 或 total + target 為奇數時，直接回傳 0。

每個數字只能用一次，所以 s 由右往左掃。更新 dp[s] 時，dp[s − x] 還沒被這一輪改過，代表「不含 x」的方法數；若由左往右，x 會被重複使用。

nums 裡的 0：x = 0 時 dp[s] += dp[s]，每個方法數翻倍，對應 +0 與 −0 兩種寫法。