P3807. 表演赛游戏分组

解题思路

两队的总评分 total_sum 是确定的。将问题转化为，在 10 个元素 中挑选出 5 个元素，使得这 5 个元素的和尽可能接近 total_sum 的一半，即 total_sum // 2。

分组与剪枝

假定元素和较小的那组为 A 组，较大的那组为 B 组。由于 sum(A) <= total_sum // 2 <= sum(B) 始终成立，因此可以只考虑小于等于 total_sum // 2 的 A 组情况即可。

回溯解法

在 10 个元素中挑选出 5 个元素的组合问题，很容易想到直接使用 回溯 来解决。由于只考虑 A 组情况，所以当发现 path_sum > total_sum // 2 时，可以进行 剪枝 操作。

动态规划解法

当然 背包 DP 也可以解决这个问题，等同于需要考虑选择元素个数的 目标和 这个问题。感兴趣的同学可以自己尝试一下。

思路展开 代码把「分成实力最接近的两队」转成一个选数问题：10 人总分 total_sum 固定，只要确定其中一队（5 人）的分数和 path_sum，另一队自然是 total_sum - path_sum，差值就是 total_sum - 2 × path_sum。约定只枚举分数和不超过 target = total_sum // 2 的那一队（较小的 A 组），这样差值恒为非负，同时砍掉了一半对称的枚举。回溯函数带 startIdx 参数做组合式枚举：每层只从 startIdx 往后选人，避免同一组人按不同顺序被重复枚举。递归有两个出口：path_sum 一旦超过 target 立即剪枝返回（继续加人只会更大，这种选法对应的已不是较小那组）；path_len 恰好等于 5 时用 total_sum - 2 × path_sum 更新最小差值 ans。这份实现没有显式回滚操作，因为 path_sum、path_len 都以函数参数传递，随递归返回天然复原。

复杂度分析

• 人数固定 10、每队固定 5 人，回溯枚举的完整方案数至多为组合数 C(10,5) = 252，状态树节点总数同为常数级；每个节点的处理只是 O(1) 的加法与比较。因此时间复杂度为 O(C(10,5))，即常数量级，path_sum 超过 target 的剪枝还会进一步减少实际访问节点。
• 空间复杂度为 O(1)：递归深度不超过 5，除输入数组外无额外数据结构。

边界与注意事项

• 代码按题意写死了规模：循环范围 range(startIdx, 10)、终止条件 path_len == 5，只适用于「10 人分两队各 5 人」的场景。
• target 用整除 total_sum // 2 向下取整：总分为奇数时两队之和必为一奇一偶，差值最小只能是 1，向下取整恰好对应较小那组的上限，不会漏解。
• ans 初始化为 total_sum，是差值不可能超过的上界，保证第一个完整方案必能刷新它。
• 剪枝条件是 path_sum > target 而非 >=，因此和恰好等于 target 的选法（总分为偶数时差值为 0 的完美分法）仍会被保留。