线性动态规划：分割等和子集（Partition Equal Subset Sum）的变种——统计所有不同的分割方案数 题目描述 给定一个非空整数数组 nums ，数组中的元素都是正整数。问：有多少种不同的方式，可以将数组分割成两个子集，使得两个子集的元素和相等。 注意： 每个元素必须属于且仅属于其中一个子集（即划分是完整的）。 两个子集是无序的，即 (子集A, 子集B) 与 (子集B, 子集A) 视为同一种分割方案。 如果无法分割成等和子集，则结果为 0。 示例 输入： nums = [1, 2, 3, 3] 输出：2 解释：有两种分割方式： 子集1: {1, 2, 3}，子集2: {3}（和均为 6） 子集1: {1, 3}，子集2: {2, 3}（和均为 4） 注意 {2, 3} 与 {1, 3} 互换不算新方案。 解题步骤 第一步：问题转化 设数组所有元素的总和为 sum 。 若 sum 是奇数，则不可能分割成两个和相等的子集，直接返回 0。 若 sum 是偶数，则目标子集的和应为 target = sum / 2 。 问题转化为：从 nums 中选取若干元素，使得它们的和恰好为 target 。 但这里不是问“是否存在”，而是问 有多少种不同的选取方案 。 第二步：定义动态规划状态 设 dp[i][s] 表示 从前 i 个元素中选取若干，使得它们的和恰好为 s 的方案数 。 其中 i 从 0 到 n （ n 是数组长度）， s 从 0 到 target 。 第三步：状态转移方程 对于第 i 个元素（对应 nums[i-1] ，方便索引）： 不选第 i 个元素 ：方案数等于 dp[i-1][s] 。 选第 i 个元素 （仅当 s >= nums[i-1] 时可行）：方案数等于 dp[i-1][s - nums[i-1]] 。 因为我们要统计所有方案，所以两种情况是相加的： \[ dp[ i][ s] = dp[ i-1][ s] + dp[ i-1][ s - nums[ i-1]] \quad (\text{若 } s \ge nums[ i-1 ]) \] 否则： \[ dp[ i][ s] = dp[ i-1][ s ] \] 第四步：初始条件 dp[0][0] = 1 ：从前 0 个元素中选和为 0 的方案数为 1（什么都不选）。 dp[0][s] = 0 （当 s > 0 ）：没有元素可选，和为正数是不可能的。 第五步：最终答案 dp[n][target] 表示从所有 n 个元素中选取若干，和为 target 的方案数。 但注意：我们统计的是 选取一个子集 的方案数，而题目要求的是 将整个数组分割成两个等和子集 的方案数。 因为两个子集是无序的，所以直接返回 dp[n][target] / 2 即可吗？ 不对 ：如果 target = 0 ，分割是唯一的（两个空子集），但通常 target > 0 ，此时每个方案 (子集A, 子集B) 会被我们统计两次（一次选子集A，一次选子集B）。 因此最终答案应为： \[ \text{answer} = \frac{dp[ n][ target ]}{2} \] 但需要注意：如果 target = 0 （即所有元素和为 0），则只有一种分割方案（两个空子集），直接返回 1。 第六步：边界与优化 如果 target = 0 ，则所有元素必须全不选才能和为 0，但元素都是正整数，所以只有当数组为空时才可能，而题目说非空，所以 target = 0 实际不会出现（因为元素为正整数，和 > 0）。 空间优化：可以用一维数组 dp[s] 从后向前更新，避免覆盖。 举例演算 以 nums = [1, 2, 3, 3] 为例： 总和 sum = 9 （奇数），无法分割？等等，总和是 9，是奇数，但示例输出是 2，说明题目允许 不一定用完所有元素 吗？ 仔细看示例： [1, 2, 3, 3] 总和是 9，但示例分割为 {1, 2, 3} 和 {3} ，总和分别为 6 和 3，并不相等！ 啊，这里发现 我读错题目了 ！原来示例中两个子集的和并不相等？ 检查示例： {1, 2, 3} 和 {3} 和分别为 6 和 3，不相等。 这说明示例有误？其实原题 分割等和子集 是要求两个子集的和相等，所以示例应该是错误的。 我们重新设定一个正确示例。 修正后的示例 输入： nums = [1, 2, 3, 4] 总和 = 10，target = 5。 可能的子集和为 5 的方案： {1, 4} {2, 3} 只有这两种选取方案。 因为两个子集无序，所以整个数组的分割方案： 子集A = {1, 4}，子集B = {2, 3} 子集A = {2, 3}，子集B = {1, 4} 这两种是同一种分割，所以最终答案 = 1。 但根据我们的公式： dp[4][5] = 2 ，除以 2 得 1，正确。 动态规划表推导（nums = [ 1, 2, 3, 4]，target = 5） 初始化： dp[0][0] = 1 ，其他 dp[0][s] = 0 。 i=1（元素1） s=0: dp=1 s=1: dp=1 其他s: 0 i=2（元素2） s=0: 1 s=1: 1 s=2: 1（选2） s=3: 1（选1和2） i=3（元素3） s=0: 1 s=1: 1 s=2: 1 s=3: 2（不选3: dp[ 2][ 3]=1；选3: dp[ 2][ 0 ]=1） s=4: 1（选1和3） s=5: 1（选2和3） i=4（元素4） s=0: 1 s=1: 1 s=2: 1 s=3: 2 s=4: 2（不选4: dp[ 3][ 4]=1；选4: dp[ 3][ 0 ]=1） s=5: 2（不选4: dp[ 3][ 5]=1；选4: dp[ 3][ 1 ]=1） 最终 dp[4][5] = 2 ，除以 2 得 1，与手动分析一致。 最终实现注意 由于元素都是正整数， target 不会太大。 如果 target 为 0，应直接返回 1（只有一种分割：两个空子集），但题目元素为正整数，所以 target >= 1 。 结果可能很大，需用 long 或取模。 时间复杂度与空间复杂度 时间复杂度：O(n × target) 空间复杂度：O(target)（一维优化） 总结 这个问题是“分割等和子集”的计数版本，关键在于： 转化为子集和问题。 使用动态规划统计方案数。 最后除以 2 消除有序性（因为两个子集互换视为同一种分割）。