当前位置：首页 > news >正文

416. 分割等和子集

news 2026/9/2 4:46:52

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)

预判 (Pre-check)：

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

初始化 (Init)：

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

递归 (Recursion)：

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

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

记忆 (Store)：将结果存入memo并返回。

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

// 题目：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(3, 11): (当前物品 5)

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

进入分支dfs(2, 6): (当前物品 11)

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

进入分支dfs(1, 6): (当前物品 5)

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

进入分支dfs(0, 1): (当前物品 1)

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

终止条件 (Base Case):

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

回溯 (Unwind):

- 所有递归调用链层层返回 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 迭代)

预判 (Pre-check)：

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

初始化 (Init)：

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

填表 (Tabulation)：

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

结果：返回f[n][target]。

🔍 代码回忆清单

// 题目：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]; } }