分割等和子集（Partition Equal Subset Sum） 题目描述 给定一个只包含正整数的非空数组 nums ，判断是否可以将该数组分割成两个子集，使得两个子集的元素和相等。 例如： 输入： nums = [1, 5, 11, 5] 输出： true 解释：数组可以分割为 [1, 5, 5] 和 [11] ，两个子集的和均为 11。 输入： nums = [1, 2, 3, 5] 输出： false 解释：无法分割成两个和相等的子集。 解题过程循序渐进讲解 步骤 1：问题转化 若数组总和 sum 为奇数，直接返回 false ，因为无法分割为两个和相等的整数子集。 若总和为偶数，设目标值 target = sum / 2 。问题转化为：是否存在一个子集，其元素和等于 target ？ 若能找到这样的子集，剩余元素自然构成另一个和为 target 的子集。 步骤 2：定义状态 定义 dp[i][j] 表示：考虑前 i 个元素时，是否存在一个子集的和恰好为 j 。 i 的取值范围： 0 到 n （ n 为数组长度）。 j 的取值范围： 0 到 target 。 步骤 3：状态初始化 dp[0][0] = true ：不选任何元素时，和为 0 是可能的。 对于 j > 0 ， dp[0][j] = false ：没有元素可选时，无法得到正数和。 步骤 4：状态转移方程 对于每个元素 nums[i-1] （第 i 个元素）和每个目标和 j ： 若 j < nums[i-1] ：当前元素太大，不能选。 dp[i][j] = dp[i-1][j] （继承前 i-1 个元素的结果）。 若 j >= nums[i-1] ：可选或不选当前元素。 不选： dp[i][j] = dp[i-1][j] 选： dp[i][j] = dp[i-1][j - nums[i-1]] 两者满足其一即为 true ，因此： dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]] 步骤 5：空间优化 观察状态转移方程， dp[i][j] 仅依赖于 dp[i-1][...] ，可优化为一维数组： 定义 dp[j] 表示：是否存在子集和为 j 。 初始化： dp[0] = true ，其余为 false 。 遍历每个元素 num ， 从后向前 更新 j （ target 到 num ）： dp[j] = dp[j] || dp[j - num] 注意：从后向前更新避免重复使用同一元素。 步骤 6：实例演示 以 nums = [1, 5, 11, 5] 为例： 总和 sum = 22 ， target = 11 。 初始化 dp = [true, false, ..., false] （长度 12）。 遍历元素： num = 1 ：更新 j = 11→1 ， dp[1] = dp[1] || dp[0] = true 。 num = 5 ：更新 j = 11→5 ， j=11 ： dp[11] = dp[11] || dp[6] = false j=10 ： dp[10] = dp[10] || dp[5] = false j=6 ： dp[6] = dp[6] || dp[1] = true j=5 ： dp[5] = dp[5] || dp[0] = true num = 11 ：更新 j = 11 ， dp[11] = dp[11] || dp[0] = true ，已满足条件。 最终 dp[11] = true ，返回 true 。 步骤 7：复杂度分析 时间复杂度： O(n × target) 空间复杂度： O(target) 步骤 8：核心思路总结 通过动态规划将问题转化为子集和问题，利用背包思想逐步构建可达的和，最终判断 target 是否可达。