分割等和子集为什么是 0-1 背包？一维 DP 为什么要倒序？
简化版
分割等和子集先求总和，若总和为奇数直接失败；否则问题变成能否从数组中选出若干数，使和等于 sum/2。这是 0-1 背包可行性问题，dp[j] 表示是否能凑出和 j，每个数只能用一次，所以容量必须倒序遍历。
详细版
设目标为 target = sum / 2。初始化 dp[0]=true，表示什么都不选可以凑出 0。遍历每个数字 num，对 j 从 target 倒序到 num，若 dp[j-num] 为真，则 dp[j]=true。最后返回 dp[target]。
倒序的原因是避免同一个 num 在本轮被重复使用。如果正序遍历，刚更新出的 dp[j] 可能马上被同一轮后面的状态使用，变成完全背包。时间复杂度 O(n * target)，空间复杂度 O(target)。
完整版教学
一、为什么能转成目标和为一半
如果数组能分成两个和相等的子集，设总和为 sum，两个子集和都必须是 sum / 2。所以前置条件是 sum 必须为偶数。
nums = [1,5,11,5]
sum = 22
target = 11
可选 [11] 或 [1,5,5]因此问题变成：能否选出一些元素，使它们的和正好等于 11。
二、为什么这是 0-1 背包
每个数组元素只有两种选择：选或不选；不能重复选。这正是 0-1 背包。
| 背包概念 | 本题对应 |
|---|---|
| 物品 | 数组中的每个数 |
| 重量 | 数字本身 |
| 容量 | sum / 2 |
| 目标 | 是否能刚好装满 |
记忆钩子：只要看到“每个数用一次，凑出某个和”，优先联想到 0-1 背包可行性。
三、二维 DP 如何定义
可以先从二维状态理解：
dp[i][j]：只使用前 i 个数，能否凑出和 j转移有两种：
不选 nums[i-1]：dp[i][j] = dp[i-1][j]
选 nums[i-1]：dp[i][j] = dp[i-1][j - nums[i-1]]最终取二者或：
dp[i][j] = dp[i-1][j] || dp[i-1][j - num]四、一维压缩为什么必须倒序
一维 dp[j] 表示当前处理过的数字能否凑出 j。处理 num 时，dp[j] 应该来自上一轮的 dp[j-num]，而不是本轮刚更新的状态。
nums = [2], target = 4
若正序：
dp[2] = true
随后 dp[4] 可能由本轮 dp[2] 推出 true
等价于把 2 用了两次倒序遍历可以保证 dp[j-num] 仍是上一轮结果。
五、代码模板
boolean canPartition(int[] nums) {
int sum = 0;
for (int x : nums) sum += x;
if ((sum & 1) == 1) return false;
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}如果在遍历过程中 dp[target] 已经为真，可以提前返回，但要确保题目只要求存在性。
六、和完全背包的遍历顺序对比
| 类型 | 每个物品使用次数 | 一维遍历方向 |
|---|---|---|
| 0-1 背包 | 最多一次 | 倒序 |
| 完全背包 | 可重复使用 | 正序 |
这张表是背包题的高频追问。分割等和子集属于 0-1 背包，所以倒序。
七、常见误区与追问
- 误区：总和为偶数就一定能分。 偶数只是必要条件，还要看是否存在子集和为一半。
- 误区：一维 DP 正序遍历。 正序会让同一个数在本轮被重复使用。
- 误区：把 dp[j] 定义成最大价值。 本题只问能否凑出目标，用 boolean 更直接。
- 追问：为什么
dp[0]=true？ 什么都不选可以凑出 0，是后续状态的起点。 - 追问：复杂度和什么有关？ 与
n * sum/2有关，是伪多项式复杂度。 - 追问：如果有负数还能这么做吗？ 经典背包容量模型依赖非负整数，含负数需要改状态表示。
八、加强记忆
分割等和子集要先从“两个集合和相等”转成“找一个集合凑出总和一半”。这个转换完成后，它就是最标准的 0-1 背包可行性：物品是数字，容量是 target，状态是能否凑出某个和。写一维 DP 时牢牢记住“每个数只能用一次，所以倒序”，用 [2] target=4 这个反例就能解释正序为什么错。