算法面试问题：如何将数组拆分为两个等长且和相等的子数组？

问题回顾 #

给定长度为偶数n的数组，需将其划分为两个长度均为n/2的子数组，要求两子数组的和相等；若无法实现则返回-1。

第一步：先做可行性快速判定 #

先排除绝对不可能的情况，避免做无用功：

• 计算数组总和total_sum，若total_sum % 2 != 0，直接返回-1——因为两个等和子数组的和必然是总和的一半，总和为奇数时不可能满足。
• 计算目标子数组和target = total_sum / 2，若数组中存在单个元素大于target，直接返回-1——该元素无论放入哪个子数组，都会导致其和超过目标值。

可行解法思路 #

1. 回溯剪枝（适合n ≤ 20的小规模场景） #

核心是尝试挑选n/2个元素，验证其和是否等于target，过程中通过剪枝减少无效递归：

• 递归遍历数组，维护三个状态：当前遍历到的元素索引、已选中元素的数量、已选中元素的和，以及选中元素的列表。
• 剪枝规则：
  • 若当前和已超过target，直接终止当前分支。
  • 若已选中元素数量超过n/2，直接终止当前分支。
  • 若剩余未遍历元素的数量 + 已选中数量 < n/2，说明后续无法凑够n/2个元素，直接终止当前分支。
• 当已选中元素数量恰好为n/2且和等于target时，即可得到一组解：选中的元素为一个子数组，剩下的元素为另一个子数组。

2. Meet-in-the-Middle（适合n ≤ 40的中等规模场景） #

利用分治思想降低枚举复杂度：

• 将原数组平分为左右两个子数组，每个子数组长度为n/2。
• 对左半部分，枚举所有可能的子集，记录每个子集的元素数量、子集和以及对应的元素列表。
• 对右半部分，同样枚举所有子集，对于每个子集的(k, s)（k为元素数量，s为和），在左半部分的记录中查找是否存在(n/2 - k, target - s)的子集。若存在，合并两个子集的元素，即可得到符合要求的n/2个元素，剩下的元素构成另一个子数组。

3. 动态规划（可记录路径的严谨解法） #

通过状态记录可行性，同时回溯得到具体解：

• 定义dp[i][j][k]表示前i个元素中选j个元素，和为k是否可行，同时维护路径记录数组。
• 初始状态：dp[0][0][0] = true。
• 状态转移：对于第i个元素，有两种选择：
  • 选中它：若j+1 ≤ n/2且k + arr[i-1] ≤ target，则dp[i][j+1][k+arr[i-1]] = dp[i-1][j][k]，并记录选择路径。
  • 不选中它：dp[i][j][k] = dp[i-1][j][k]。
• 最终若dp[n][n/2][target]为true，则通过回溯路径数组得到选中的元素，进而拆分出两个子数组。

关于你提到的随机交换方法的问题 #

这种启发式方法存在本质缺陷：

• 无法严谨判定“不可行”：即使迭代很多次找不到解，也无法确定是真的没有解，还是当前随机策略没碰运气找到。
• 容易陷入局部最优：可能出现两数组和的差值卡在某个小值，无法进一步缩小的情况。
• 若一定要用，可设置迭代次数上限（比如1e5次），超过上限则判定为无解，但这只是经验性判断，并非严谨结论。

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