分割等和子集
Partition Equal Subset Sum
判断能否把数组分成两个子集，使两部分的元素和相等。
在力扣中练习题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
解题思路
二维 DP · 0/1 背包
先算总和，再把问题变成“能否凑出总和的一半”
把数组分成两半、枚举所有子集是 2^n。先做一个必要判断：两部分和相等，总和必须是偶数；设目标容量 target = sum / 2，问题就变成“能否从数组里选出若干数，和恰好为 target”。
每个数只有选或不选两种命运。设 dp[i][j] 表示前 i 件物品能否凑出容量 j：
dp[i][j] = dp[i-1][j] 不选第 i 件
或 dp[i-1][j - nums[i-1]] 选第 i 件
自拟主例 nums = [2,3,5,6]，总和 16，目标 8。前两件凑不出 8；加入 5 后，3+5 让目标格第一次变 T；加入 6 后，2+6 也让“不选 6”这条继承路径成立。
第 2 件重量 3：容量 8 = 不选（F）或 选（F），得 F。
- i
- 2
- num
- 3
dp[i][j]：前 i 件物品能否凑出容量 j；目标容量 = 总和 16 / 2 = 8
dp[1][8] = FF—dp[1][5] = FF—压成一维时 j 必须从右向左：dp[j - num] 还得是上一件物品的值。
dp[2][8]=dp[1][8] or dp[1][5]F or F=F初值：容量 0 对所有前缀都可达（一件都不选），所以第 0 列全为 true；第 0 行除容量 0 外都是 false。
dp[i][j]：前 i 件物品能否凑出容量 j；目标容量 = 总和 16 / 2 = 8
dp[3][8] = TT✓dp[3][2] = TT✓压成一维时 j 必须从右向左：dp[j - num] 还得是上一件物品的值。
dp[4][8]=dp[3][8] or dp[3][2]T or T=T并列最优 T
3 + 5时间 O(n × target)，空间 O(n × target)。
易错点
- 忘记先判断总和奇偶：奇数永远不可能平分，后面的表算了也没用。
- 把 dp[i][j] 定义成“前 i 件里有没有和为 j 的子集”却漏掉不选当前件的继承项。
- target 可能为 0（全 0 数组），此时应直接返回 true；代码里 dp[*][0] 已经处理。
一维滚动 · 倒序更新
二维表压成一行，容量从右往左扫
时间相同，空间从 O(n × target) 降到 O(target)；代价是 j 必须倒序，否则同一件物品会被重复使用。
转移只依赖上一行，所以可以把第一维压掉，只保留 dp[j]。但这里有一个关键顺序：j 必须从 target 往左走。
正序时，dp[j - num] 可能已经在本次物品循环中被更新过，相当于把当前物品用了两次；倒序时，dp[j - num] 还停留在上一件物品的状态，正好符合 0/1 背包的约束。
写成代码就是：
for (int j = target; j >= num; --j)
dp[j] = dp[j] || dp[j - num];
时间 O(n × target)，空间 O(target)。如果题目还要求输出具体选了哪些数，一维数组无法直接回溯，需要额外记录选择或保留二维表。
- 1总和奇数返回 false，target = sum / 2。
- 2dp[0] = true，其余 false。
- 3逐件物品，j 从 target 倒序到 num。
- 4dp[j] = dp[j] || dp[j-num]。
- 5返回 dp[target]。
易错点
- j 正序遍历：dp[j-num] 已被当前物品更新，等于允许重复选同一件。
- 循环条件写成 j > num：漏掉 j == num 时正好由 dp[0] 转移来的情况。
- dp[0] 没有初始化为 true：所有容量都从 0 起跳，整个表会全假。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [2,3,5,6]总和 16，目标容量 8；容量 0 对所有前缀都可达，其余先记为 F。
- target
- 8
dp[i][j]：前 i 件物品能否凑出容量 j；目标容量 = 总和 16 / 2 = 8
压成一维时 j 必须从右向左：dp[j - num] 还得是上一件物品的值。
dp=T查看 C++ 代码
延伸阅读
- 这是 0/1 背包的判定版：物品重量和价值都是 nums[i]，问能否恰好装满 target。
- 若题目要求的是“最少分成几个等和子集”或“分成 k 个等和子集”，状态需要再增加一维。