416. 分割等和子集

416. 分割等和子集

中等

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

📝 核心笔记：分割等和子集 (Partition Equal Subset Sum)

1. 核心思想 (一句话总结)

“0/1 背包问题：把这一堆数字看作物品，能不能从中挑出一些物品，刚好填满容量为 TotalSum / 2 的背包？”

• 转化：只要找到一个子集和等于总和的一半，剩下的元素和自然也是一半。
• 状态：dfs(i, j) 询问“在前 i 个物品中，能不能凑出和为 j？”
• 选择：对于每个数字 nums[i]，只有两种选择——选它 或者 不选它。

2. 算法流程 (DFS + Memo)

• • 计算总和 s。如果 s 是奇数，绝对无法二等分，直接返回 false。
  • 目标背包容量 target = s / 2。

• • 创建 memo[n][target + 1]。
  • 填充 -1 表示“未知领域”。

• • 终止条件 (Base Case)：物品用完了 (i < 0)。如果此时背包刚好空了 (j == 0)，成功；否则失败。
  • 查表：如果 memo[i][j] != -1，直接返回记录过的值。
  • 决策：

• • • 选：dfs(i – 1, j – nums[i]) (前提是背包够装 j >= nums[i])。
    • 不选：dfs(i – 1, j)。
    • 只要任一路径成功 (||)，结果即为真。

🔍 代码回忆清单 (带注释版)

// 题目：LC 416. Partition Equal Subset Sum
class Solution {
public boolean canPartition(int[] nums) {
int s = 0;
for (int num : nums) {
s += num;
}
// 1. 奇数无法分割
if (s % 2 != 0) {
return false;
}

int n = nums.length;
int target = s / 2;
// 2. 记忆化数组：n 个物品，背包容量 target
// 使用 int 而不是 boolean，为了区分 null/true/false 三种状态
int[][] memo = new int[n][target + 1];
for (int[] row : memo) {
Arrays.fill(row, -1); // -1 表示没有计算过
}

// 从最后一个物品开始决策，目标是填满 target
return dfs(n – 1, target, nums, memo);
}

private boolean dfs(int i, int j, int[] nums, int[][] memo) {
// 3. Base Case: 物品耗尽
if (i < 0) {
return j == 0; // 如果容量刚好减完，说明凑出来了
}

// 4. 查备忘录
if (memo[i][j] != -1) {
return memo[i][j] == 1;
}

// 5. 核心状态转移
// 选 nums[i]: 前提是 j >= nums[i]
// 不选 nums[i]: 直接跳过看 i-1
boolean res = (j >= nums[i] && dfs(i – 1, j – nums[i], nums, memo)) ||
dfs(i – 1, j, nums, memo);

memo[i][j] = res ? 1 : 0; // 记忆化：记录结果
return res;
}
}

⚡ 快速复习 CheckList (易错点)

• [ ] 为什么判断奇偶性很重要？

• • 如果不判断，s / 2 会向下取整（例如 sum=11, target=5），这会导致寻找错误的子集和，逻辑完全崩塌。

• [ ] Memo 数组为什么是 int？

• • 如果用 boolean[][]，默认值是 false。
  • 当 dfs 经过计算确实返回 false 时，你无法区分它是“算过了且为假”还是“还没算过”。会导致重复计算超时。

• [ ] 递归方向？

• • dfs(n-1, target) 是自顶向下。
  • 对应的 DP 迭代写法是从 0 到 target 填表。

🖼️ 数字演练

nums = [1, 5, 11, 5] 总和 Sum = 22, 目标 Target = 11。

• • 尝试 不选: dfs(2, 11)。
  • 尝试 选: dfs(2, 6) (11 – 5)。

• • 选: 6 – 11 < 0。背包不够装，不能选。
  • 不选: 只能调用 dfs(1, 6)。

• • 尝试 选: dfs(0, 1) (6 – 5)。

• • 尝试 选: dfs(-1, 0) (1 – 1)。

• • i = -1, j = 0。物品用完了，且背包容量刚好减为 0。返回 True。

• • 所有递归调用链层层返回 True。

📝 核心笔记：分割等和子集 (Partition Equal Subset Sum) 递推

1. 核心思想 (一句话总结)

“填表游戏：我们有一排格子（容量 0 到 Target），每一个新来的数字都试图去勾选新的格子——要么继承上一行的结果，要么在上一行已有的结果上加上自己。”

• 状态定义：f[i][j] 表示“在前 i 个数字中，能否凑出和为 j”。
• 转移方程：f[i+1][j] = f[i][j] || f[i][j – nums[i]]。

• • f[i][j]：不选当前数字（直接继承上一行的结果）。
  • f[i][j – nums[i]]：选当前数字（看上一行能不能凑出 j – x）。

2. 算法流程 (DP 迭代)

• • 求和 s。如果是奇数，无法平分，返回 false。
  • 目标容量 target = s / 2。

• • boolean[][] f 大小为 [n + 1][target + 1]。
  • Base Case：f[0][0] = true。表示“从 0 个数字中凑出和为 0”是可能的（一个都不选）。

• • 外层循环 i：遍历每一个数字 nums[i]。
  • 内层循环 j：遍历每一个容量从 0 到 target。
  • 转移：如果 j >= x，看“不选”或“选”两个来源；否则只能“不选”。

🔍 代码回忆清单

// 题目：LC 416. Partition Equal Subset Sum
class Solution {
public boolean canPartition(int[] nums) {
int s = 0;
for (int num : nums) {
s += num;
}
// 1. 奇数无法平分，直接剪枝
if (s % 2 != 0) {
return false;
}
s /= 2; // 目标变为总和的一半
int n = nums.length;

// 2. DP 表：f[i][j] 表示前 i 个物品能否凑出 j
// 这里的 i+1 对应 nums[i]，是为了处理 f[0] (0个物品) 的情况
boolean[][] f = new boolean[n + 1][s + 1];
f[0][0] = true; // Base Case: 0个物品凑出0是真

// 3. 外层：遍历物品
for (int i = 0; i < n; i++) {
int x = nums[i];
// 4. 内层：遍历容量
for (int j = 0; j <= s; j++) {
// 状态转移：不选 (继承上一行) || 选 (找上一行 j-x 的位置)
// f[i+1] 代表当前行，f[i] 代表上一行
f[i + 1][j] = (j >= x && f[i][j – x]) || f[i][j];
}
}
// 5. 返回右下角
return f[n][s];
}
}

⚡ 快速复习 CheckList (易错点)

• [ ] 为什么行数是 n + 1？

• • 为了方便初始化 f[0][0] = true（表示没有物品时的状态）。
  • 如果只开 n 行，处理第一个物品时需要单独写 if 判断，代码会很乱。n+1 是一种常用的哨兵技巧。

• [ ] 能不能优化成一维数组？

• • 可以（这是面试常考点）。
  • 状态方程 f[j] = f[j] || f[j – x]。
  • 关键点：内层循环 j 必须 从大到小 (倒序) 遍历。防止同一个物品在同一轮被多次使用（避免变成了完全背包）。

• [ ] 初始化 f[0][0] 的重要性

• • 如果没有这就全完了。所有的 true 都是从这就 f[0][0] 像病毒一样扩散出去的。

🖼️ 数字演练

nums = [1, 5, 11, 5] 总和 = 22, 目标 Target = 11。

• • f[0][0] = True。其余全是 False。

• • 继承上一行 f[0][0] -> f[1][0] = T。
  • 加上 1: f[0][0] -> f[1][1] = T。
  • 当前有效和: {0, 1}。

• • 继承上一行: {0, 1} 为 T。
  • 加上 5: 0+5=5, 1+5=6。
  • 当前有效和: {0, 1, 5, 6}。

• • 继承上一行: {0, 1, 5, 6} 为 T。
  • 加上 11: 0+11=11 (Target 达成!), 1+11=12…
  • 当前有效和: {0, 1, 5, 6, 11, …}。