LeetCode LCR 101. 分割等和子集
题目描述
题意分析
判断能否把全部正整数分成两个互不相交、元素和相等的子集，不要求元素在原数组中连续，也不需要输出具体划分。
设总和为 $S$。若 $S$ 为奇数就不可能平分；否则只需找到一个和为
target = S / 2的子集，剩余元素之和自然也是target。每个数组位置只能使用一次。
解法：01 背包判断半和可达
核心思路
[!blue]
判断子集是否存在时，只需知道处理过的元素能凑出哪些和，不必保存它们的具体组成。定义
dp[j]为：只用已经处理过的元素，能否选出和恰好为j的子集。初始只有空集可用，因此dp[0] = true，其余位置为假。处理当前元素
x时，和j有两种来源：不选x，沿用原来的dp[j]；选x，则此前必须能凑出j - x。两者任一成立即可，所以转移为dp[j] = dp[j] || dp[j - x]。两个来源都必须基于处理
x之前的状态。由于x > 0，下标j - x小于j，从target向下更新时，较小位置尚未在本轮改写，读到的仍是旧状态；这样每个位置的x最多使用一次。若正序更新，就可能把本轮刚加入的x再用一遍。只保存不超过
target的和即可，因为正数继续相加不可能让更大的和降回来。所有元素处理完后，dp[target]就回答是否存在所需子集。空集只用于启动递推：合法均分时target > 0，找到半和后两边都会非空。
解题步骤
- 求总和，奇数直接返回
false。- 创建长度为
target + 1的布尔数组，只将dp[0]设为真。- 逐个处理
x，令j从target递减到x，合并选与不选的可达状态。- 返回
dp[target]。
代码实现
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int x : nums) {
sum += x;
}
// 奇数无法平分，直接否定。
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int x : nums) {
// 倒序遍历，保证 dp[j - x] 读到的是尚未使用 x 的旧值。
for (int j = target; j >= x; --j) {
dp[j] = dp[j] || dp[j - x];
}
}
return dp[target];
}
}
func canPartition(nums []int) bool {
sum := 0
for _, x := range nums {
sum += x
}
// 奇数无法平分，直接否定。
if sum%2 != 0 {
return false
}
target := sum / 2
dp := make([]bool, target+1)
dp[0] = true
for _, x := range nums {
// 倒序遍历，保证 dp[j-x] 读到的是尚未使用 x 的旧值。
for j := target; j >= x; j-- {
dp[j] = dp[j] || dp[j-x]
}
}
return dp[target]
}
复杂度分析
- 时间复杂度：$O(nT)$，其中 $n$ 为元素个数，$T=S/2$ 为目标和。题目约束使 $T\le10000$。
- 空间复杂度：$O(T)$，保存从 0 到目标和的可达状态。
关键点总结
[!green]
- 一个半和子集确定后，另一半就是它的补集，无需再做一次搜索。
dp表示能否达到，转移使用逻辑或，不能用当前分支覆盖已有的真值。- 单个正数无法均分，同一套奇偶判断与背包循环就会返回假。
易错点总结
[!yellow]
- 未检查总和奇偶便整除，会把无法平分的输入转换成错误目标。
- 漏掉
dp[0] = true，所有后续状态都无法成立。- 容量正序会重复使用当前元素，违反每个位置最多选一次的要求。
- 当
j < x时不能读取dp[j - x]；大于目标的元素在本轮自然跳过。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 494. 目标和 | 中等 | 都能转成0/1子集和，本题只判断能否取到总和一半，原题统计赋号方案数。 |
| 1049. 最后一块石头的重量 II | 中等 | 同样把元素分成两组，原题最小化两组和之差，本题要求差恰为0。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！