解題說明
Partition Equal Subset Sum（416）
題目描述：給定一個正整數陣列 nums，判斷是否可以將其分割為兩個子集，使得兩個子集的元素總和相等。
解題思路：本題是0/1 背包問題的經典應用。
關鍵觀察：若陣列總和為 total，要分成兩個相等的子集，則每個子集的和必須為 target = total / 2。若 total 為奇數，直接回傳 false。
問題轉化為：能否從 nums 中選取若干元素，使其總和恰好等於 target？
DP 定義：dp[j] = 布林值，代表「是否能從當前考慮的元素中選取子集，使得總和恰好為 j」。
轉移方程：dp[j] = dp[j] || dp[j - nums[i]]
- 對每個數字
nums[i]，從右到左更新（避免同一元素被重複使用）。 dp[j - nums[i]]為 true 表示不選nums[i]時能湊出j - nums[i]，加上nums[i]後就能湊出j。
初始化：dp[0] = true（和為 0 永遠可達，選空集即可）。
答案：dp[target]。
C++ 解法
複雜度分析
時間複雜度：O(n × target) = O(n × sum/2) — 對每個元素進行一次 O(target) 的內層迴圈，n 為陣列長度，sum 為陣列總和。
空間複雜度：O(target) = O(sum/2) — 只需一個長度為 target+1 的一維 DP 陣列（相較於二維 DP 的空間優化版）。
虛擬碼
1. Compute total = sum of all nums.
2. If total is odd, return false.
3. Set target = total / 2.
4. Initialize dp[0..target] = false; dp[0] = true.
5. For each num in nums:
a. For j from target down to num:
- dp[j] = dp[j] OR dp[j - num]
b. If dp[target] is true, return true early.
6. Return dp[target].其他解法
二維 DP O(n × target) 時間，O(n × target) 空間：dp[i][j] = 考慮前 i 個元素能否湊出和為 j，轉移為 dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]。邏輯清晰但空間消耗較大，可壓縮至一維。
Bitset 優化 O(n × target / 64) 時間：用一個 bitset 代替布林陣列，bits |= (bits << num) 一行即可完成內層迴圈。在 target 較大時（例如 10000+），bitset 的位元運算可帶來顯著常數加速，是競程常見技巧。
延伸思考
- 若問題改為「分成 k 個總和相等的子集」（Partition to K Equal Sum Subsets，LeetCode 698），應改用什麼演算法？時間複雜度如何？
- 本題要求兩個子集和「完全相等」。若放寬條件為「兩個子集和之差的絕對值最小」，DP 的目標如何修改？
- 若陣列中的數字可以為負數，本題的解法需要做哪些調整？