如何将整数数组划分为和最接近的两组？有无快于回溯的解法？

开发者阿泽

2026-5-20

有没有比回溯法更快的数组等和划分方案？

当然有！回溯法虽然思路直观，但它的时间复杂度是O(2^n)，数组元素稍微多几个（比如n=20）就会慢到离谱。下面给你介绍几种效率高得多的解决方案，覆盖不同场景：

1. 动态规划（0-1背包变种）

这是解决这类问题最常用的高效方法，核心思路是把问题转化为「寻找最接近总和一半的子集和」：

步骤拆解：
1. 先计算数组的总总和 total_sum，我们的目标是找到最大的 subset_sum，使得 subset_sum ≤ total_sum // 2
2. 创建一个布尔数组 dp，其中 dp[i] 表示是否能从数组中选出若干元素，凑出和为 i 的子集
3. 初始化 dp[0] = True（空子集的和为0），然后遍历数组中的每个数字，从后往前更新 dp 数组（避免重复选择同一个元素）
4. 遍历完所有元素后，找到最大的 i 满足 dp[i] = True，那么两组的和就是 i 和 total_sum - i
举个例子：
题目中的数组 {2,8,10,1,3} 总和是24，目标是找≤12的最大子集和。通过动态规划可以找到12（比如2+10或者8+1+3），所以两组和都是12，完美符合要求。
复杂度：时间复杂度是O(n * S)（S是总和的一半），空间可以优化到O(S)，适合中等规模、总和不算特别大的数组。

如果数组元素数量较多（比如n在30-40之间），但总和很大，动态规划的空间会不够用，这时候分治思路的Meet-in-the-middle就更合适：

步骤拆解：
1. 将数组平均分成左右两半，分别枚举每一半的所有可能子集和，把结果存储在两个集合（或列表）中
2. 把其中一个集合排序，然后遍历另一个集合的每个元素 s，在排序后的集合里用二分查找找到最接近 (total_sum - s) 的元素，计算两者的和，找到最接近 total_sum//2 的组合
3. 最终得到的最优组合对应的和，就是两组和中的一个，另一个是总和减去这个值
复杂度：时间复杂度是**O(n * 2^{(n/2))**，比回溯法的O(2}n)快得多——比如n=40时，2^20是百万级，完全可以在短时间内处理完。

贪心的思路很简单：每次把当前剩余的最大元素放到当前和较小的组里。但要注意，这个方法不能保证得到最优解，只能作为快速近似的方案。

比如数组{3,3,2,2,2}，贪心会分成{3,3}和{2,2,2}，刚好是最优解；但如果是数组{1,2,3,4,5,6,7,8,9,10}，贪心得到的结果就不是最接近的，所以如果要求精确解，千万别用这个方法。

内容的提问来源于stack exchange，提问作者user9409795