分割等和子集：选一撮数凑出一半
总和奇数分不了。偶数就问：能否从数组里选出若干个数，加起来恰好等于 sum/2。每件只用一次，倒着更新。
sum 为奇数直接 false。否则 target=sum/2，dp[j] 表示已处理过的数能否凑出 j。对每个 num 从 j=target 倒着走到 num：dp[j] 一旦可由 dp[j−num] 推得就标真。答案看 dp[target]。时间 O(n·target)，空间 O(target)。
给你一个只含正整数的数组，问能不能把它分成两个子集，使两个子集里的数加起来一样大。每个数必须进且只进其中一个子集，不能丢掉，也不能用两次。
主例 nums = [1, 5, 11, 5]。总和 22，一半是 11。一边放 11，另一边放 1+5+5，两边都是 11，所以答案是 true。若把 11 换成 12，总和 23 是奇数，两半不可能相等，直接 false。
枚举每个数进左堆还是进右堆能做对，但是 2^n 条路。本文要回答：为什么「均分」只等于「能否凑出一半」，以及主例里那一次 dp[11] 变真，是在处理哪一个数时发生的。
倒序更新的 0-1 背包
两堆和相等，加起来就是总和，所以总和必须是偶数。奇数直接返回 false，不必再搜。偶数时，只要能选出一撮数恰好等于 target = sum/2，剩下的那撮自动也是 target。缺的不是「左堆右堆两张清单」，而是一个可递推的判定：用已经看过的数，哪些和凑得出来。
开一个布尔数组 dp，下标是和，dp[j] 表示「当前这些数里，能否选出若干个加出 j」。一开始一个数都没看，只有空集，和是 0，所以 dp[0] = true，其余全是 false。每进来一个数 num，它只有两种用法：不选，旧的 dp 原样保留；选，就在所有已经能凑出的 j−num 后面接上它，得到 j。
更新必须从 target 往 0 走。正着走会把同一件物品用两次：刚用这个 num 把 dp[j] 点亮，下一步 j+num 又读到这个新值，等于这件物品进了背包两次。那是完全背包。本题每个数最多用一次，所以倒序：大的 j 先写，写它时读到的 dp[j−num] 还是「没放进当前这个 num」的旧值。两个 5 是两件不同的物品，可以各用一次；倒序禁止的是「同一个 5 在这一轮被加两次」。
用手走主例。sum=22，target=11，dp 长度 12，只有 dp[0] 为真。先处理 1：从 j=11 往下，只有 j=1 读到 dp[0]，于是 dp[1] 变真。现在能凑的是 {0, 1}。再处理第一个 5：j=6 读到 dp[1]，j=5 读到 dp[0]，dp[5]、dp[6] 变真。能凑的是 {0, 1, 5, 6}。演示场景里这一行正是 [真, 真, 假, 假, 假, 真, 真, …]。
再处理 11。j=11 读到 dp[0]，dp[11] 立刻变真：单独一个 11 就凑满了目标。互补的那一撮是 {1, 5, 5}，和也是 11。后面那个 5 不必再看，答案已经是 true。若数组里没有 11、只有更多小的数，就要继续倒序把每一个都放进去，直到 dp[target] 被点亮，或者数用完仍是 false。
数比 target 还大，这一件选了必超，循环 j >= num 根本进不去，等于自动跳过。全是 0 时 target=0，dp[0] 一开始就是 true。只有一个数时，它必须等于 0 才能均分，否则 false。这些边界都被同一套「先看奇偶，再倒序填表」覆盖，不用另写分支。
为什么倒序正着更新时，dp[j] 刚被当前 num 点亮，后面的 j+num 会把这件物品再加一次。倒序保证读到的 dp[j−num] 还是本轮开始前的旧值。这就是 0-1 背包和完全背包的分界。
Go：0/1 背包判定
func canPartition(nums []int) bool {sum := 0for _, n := range nums { sum += n }if sum%2 == 1 { return false }target := sum / 2dp := make([]bool, target+1)dp[0] = truefor _, num := range nums {for j := target; j >= num; j-- {if dp[j-num] { dp[j] = true }}}return dp[target]}
1先加总。奇数直接 false，偶数才有一半可凑。
2dp[0]=true 是空集。其余下标表示「这个和目前凑不凑得出」。
3内层从 target 倒回 num：读到的 dp[j-num] 还没有用过当前这个 num。
4主例处理到 11 时 dp[11] 变真。最后只问这一格，不需要把子集本身还原出来。
总结
均分两半 = 0-1 背包判定能否凑满 sum/2。主例 [1,5,11,5] 在 11 上点亮 dp[11]。
- 总和奇数不可能均分。偶数只问一半，剩下的自动相等。
- 倒序更新保证每件物品只用一次；两个 5 是两件物品，可以各用一次。
- dp[0] 永远为真。数大于 target 会在 j>=num 处被跳过。