数组分配给两人使两组和相等的方法数计算及动态规划复杂度优化

题目规则回顾 #

给定数值数组，统计满足以下条件的分配方案总数：

• 分配给A、B两人的元素总价值完全相等
• A、B每人至少分到1个元素
• 可保留任意数量元素不参与分配

参考示例：
输入数组：[1,2,3,4,5,11]
输出结果：8
合法分配包含：

• A组[2,3]、B组[5]
• A组[3,4]、B组[5,2]
• A组[2,4,5]、B组[11]
• A组[3,4,5]、B组[1,11]
• A组[1,2,3,5]、B组[11]
• A组[1,2]、B组[3]
• A组[1,3]、B组[4]
• A组[1,4]、B组[5]

现有解法的瓶颈 #

当前实现的动态规划方案采用双维度状态，即同时维护A组总价值、B组总价值两个独立维度的状态，时间复杂度为O(n * sum_range * sum_range)，存在明显的冗余计算，距离面试期望的O(n * sum_range)复杂度目标有优化空间。

核心优化思路 #

状态压缩：从双维度降为单维度差值 #

原双维度状态dp[i][x][y]代表前i个元素处理后，A组总价值为x、B组总价值为y的方案数，而题目核心约束只要求最终x=y，因此无需独立跟踪x、y的具体值，只需跟踪两者的差值：

• 定义diff = sum_A - sum_B，只需最终diff = 0即可满足等和要求
• 状态简化为一维数组：dp[d]代表处理完当前已遍历元素后，A、B组总价值差值为d时的总路径数
• 差值的取值范围完全被限制在[-total_sum, total_sum]内（total_sum为数组所有元素的价值总和），总状态规模仅为2*sum_range，相比原平方级状态直接降低一个维度。

状态转移逻辑 #

每遍历到一个元素num，对当前的差值状态有三种可选操作：

1. 将元素分给A组：差值增加num，即从旧状态dp[d]转移到新状态dp[d + num]
2. 将元素分给B组：差值减少num，即从旧状态dp[d]转移到新状态dp[d - num]
3. 丢弃元素不参与分配：差值保持不变，即旧状态dp[d]直接保留在新状态中

初始状态设置为：未处理任何元素时，A、B均无元素，差值为0，对应空路径dp[0] = 1。

实现提示：由于差值可能为负数，实际编码时需给所有差值加固定偏移量（等于数组总价值），将负差值映射为非负的数组下标，避免下标越界。

结果修正规则 #

遍历完所有元素后，dp[0]的总计数包含两类不符合题目要求的路径，需要修正才能得到正确答案：

1. 剔除全空路径：也就是A、B都没有分到任何元素、所有元素都被丢弃的初始状态，这类路径仅计数1次，是不满足「每人至少1个元素」要求的
2. 消除互换重复计数：每一组合法的非空等和分配，都会在差值逻辑中被计数两次（即A拿集合X、B拿集合Y，和A拿集合Y、B拿集合X会被识别为两个独立路径），和题目示例的计数规则保持一致——示例中不将A、B角色互换计为新方案，因此最终结果需要将剩余计数除以2

最终计算公式为：
合法方案总数 = (dp[0] - 1) // 2

按示例输入计算时，代入上述公式刚好得到结果8，和示例输出完全匹配。

最终复杂度 #

优化后的整体时间复杂度为O(n * total_sum)，空间复杂度可通过滚动数组优化为O(total_sum)，完全满足面试的性能要求。

内容的提问来源于stack exchange，提问作者SuspiciousKitchen-7