华为OD机考《游戏分组》五种语言解法：DFS、背包与细节避坑

华为OD机考的C卷题库里，“游戏分组”是一道出场率相当高的题。不少人觉得它简单，真上了双机位考场，才发现一个空格就能导致判错、一个类名不对直接0分、一行调试输出就把整道题搭进去。这篇文章不打算只给一份能跑的代码，而是把Java、Python、JS、C/C++、Go五种语言的完整解法都整理出来，顺带把机考的ACM输入模式、边界条件、容易翻车的细节逐个拆开说清楚。无论你是刚开始刷题的应届生，还是想突击转岗的社招选手，花二十分钟把这道题吃透，收益比盲目刷十道简单题大得多。

1. C卷“游戏分组”原题拆解：10个人、两组5人、差值最小

1.1 题面还原与考试形式

先还原一下题面。部门准备组织团建游戏，10个人分成两组进行对抗，每组5人。每个人的能力值已经提前打过分，现在要设计一种分组方案，让两边的能力值总和尽可能接近，最后输出这个最小差值。

输入格式：一行，10个空格分隔的正整数，代表10个人的能力值。 输出格式：一个整数，表示两组能力值总和的最小差值。

示例： 输入：1 2 3 4 5 6 7 8 9 10 输出：1

解释：一种最优分组是{1,2,7,8,9}和{3,4,5,6,10}，两组能力值总和分别是27和28，差值为1。这两组无论怎么交换成员，都不可能让差值变成0，所以答案就是1。

华为OD机考采用的是ACM模式，也就是需要自己编写完整的输入输出处理，而不是像某些刷题网站那样只填一个函数体。C卷是当前题库的一个版本，考试时从题库里随机抽题，所以“游戏分组”这道题被抽中的概率不低。考试使用双机位：一台电脑用来答题，另一台手机或者平板从侧后方架起来，确保考试过程全程可见。双机位本身不会影响代码逻辑，但会影响心态——平时习惯了在IDE里反复调试，考场上就要求一遍过，所以输入输出这些“跟算法关系不大”的环节，恰恰是拉开分数差距的地方。

1.2 考点拆解：这道题真正在考什么

先别看解法，想想出题人为什么要选这道题。

第一，它在考组合枚举。10个人的分组方案总数是C(10,5) = 252种。这个规模小到可以暴力枚举，不需要任何高级数据结构。

第二，它在考最值维护。枚举过程中要不断记录当前最小差值，并且在所有方案中选出最优的。

第三，它在考ACM模式的完整闭环。思路简单，但要在考场环境下一次写对并不容易。我见过太多人挂在细节上：Java的类名不叫Main，Go用了math.Abs忘记转int，JS的readline没处理换行符，Python的input()遇到多行输入直接报错。这些都是这道题真正在考察的非算法能力。

换句话说，这是一道典型的“思路两分钟，写代码十分钟，调试半小时”的题。它不考你懂多少算法，考的是你在限定时间内能不能稳定输出。

1.3 规模预判：为什么C(10,5)小到不用优化

10个人选5个进入第一组，剩下5个人自动组成第二组。组合数是252，就算把每条递归路径完整展开，叶子节点也只有252个。算上递归过程中产生的中间状态，总量也在千级，任何语言跑起来都是毫秒级。

所以这道题的策略非常明确：不要上花哨的优化技巧，用最笨、最直接、最不可能写错的方式去解。把力气花在把输入输出写稳上，比任何剪枝优化都重要。很多人一看到“差值最小”就想到动态规划，看到“组合”就想到状态压缩，实际上在这个数据规模下，直接枚举就是最优解。

2. 两种主流解法：DFS枚举与01背包变体

2.1 DFS回溯：把“每个元素选或不选”穷举清楚

DFS是这道题的首选解法，原因就一个：好写、难错。

按数组下标从小到大遍历每个人，递归函数需要维护三个状态：

• idx：当前处理到第几个人。
• count：第一组已经选了几个人。
• sum：第一组的能力值之和。

当count等于5时，第一组选满，第二组自动确定，此时差值就是abs(total - 2 * sum)。total是10个人能力值的总和，第二组的和就是total - sum。

递归过程中每个人有两种选择：进第一组，或者不进第一组。这两种选择都继续递归，最终就覆盖了全部252种组合。

剪枝只需要一条：如果剩下的元素个数不够补满5个人，直接返回，也就是10 - idx < 5 - count时剪掉。这个剪枝能砍掉大量无效分支，让递归树的规模进一步缩小。

这个枚举方式可以用排队分水果来类比：每个人面前只有两个动作，拿或者不拿，拿满5个就结算，剩下的水果自动归另一边。整个过程不重不漏，逻辑非常直白。

2.2 01背包变体：把“组和”变成“凑数”问题

如果不想写递归，可以用01背包的思路来解。

把目标翻译一下：从10个数里选5个数，让它们的和尽量接近total / 2。定义一个布尔数组dp[c][s]，表示“从已遍历的元素中选c个数，能否凑出总和s”。

遍历每个数时，按“每个数只能用一次”的规则倒序更新：

selected 从 5 到 1： s 从 total 到 v-1： 如果 dp[selected-1][s-v] 为 True： dp[selected][s] = True

初始化dp[0][0] = True。最后在所有dp[5][s]为True的s里，找abs(total - 2 * s)最小的那个，就是答案。

这个解法的关键在倒序遍历。如果正序遍历，同一个数会被重复使用多次，那就从01背包变成完全背包了。初学者经常在这里翻车，而且一旦数组维度和更新方向写错，样例大概率全过，提交却超时或者答案错误。

不过说实话，这道题的数据范围决定了DFS已经足够，DP反而要开一个(total + 1) * 6的布尔数组，总和大一点就会额外消耗内存和循环时间。所以我的建议是首选DFS，DP可以写一遍用来加深理解，但考场上没必要冒险。

2.3 位运算枚举：另一种写起来很爽的暴力

第三种解法给喜欢简洁写法的人：用二进制掩码枚举所有10位状态，某一位是1就代表这个人进第一组。

def min_diff_by_bit(nums): n = len(nums) total = sum(nums) ans = total for mask in range(1 << n): if mask.bit_count() != n // 2: continue s = 0 for i in range(n): if (mask >> i) & 1: s += nums[i] ans = min(ans, abs(total - 2 * s)) return ans

Python里mask.bit_count()可以直接数二进制中1的个数，C++对应的是__builtin_popcount(mask)。一共1024个状态，每个状态最多数10位，性能同样没有问题。位运算解法的代码量比DFS更短，但可读性差一些，适合在函数式编程手感比较强的语言里使用。

2.4 三种解法复杂度对比

从稳定性角度出发，考场上我强烈建议使用DFS。剩下的时间可以用来检查输入输出是否规范，这比在代码里加一堆优化要有价值得多。

3. 五种语言的完整实现：能直接上手的版本

3.1 Java：类名和Scanner是你唯一的坎

Java在OD机考中有一个硬性要求：主类必须叫Main，且不能带package声明。我用Scanner读取10个整数，一次读完。递归方法做成static，因为main是static，直接调用最方便。

import java.util.Scanner; public class Main { static int[] a = new int[10]; static int total = 0; static int minDiff = Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in); for (int i = 0; i < 10; i++) { a[i] = sc.nextInt(); total += a[i]; } dfs(0, 0, 0); System.out.println(minDiff); } static void dfs(int idx, int count, int sum) { if (count == 5) { int diff = Math.abs(total - 2 * sum); if (diff < minDiff) { minDiff = diff; } return; } if (idx >= 10) { return; } if (10 - idx < 5 - count) { return; } dfs(idx + 1, count + 1, sum + a[idx]); dfs(idx + 1, count, sum); } }

这里有几个地方要特别注意。

第一，Math.abs(total - 2 * sum)不会溢出。能力值范围通常是[1, 10000]，10个加起来最多100000，int完全够用。但如果题目没给范围，稳妥起见可以声明成long。

第二，剪枝放在count == 5的判断之后。很多人喜欢把剪枝写在入口处，看起来也没问题，但要注意别把idx >= 10和剪枝顺序搞反，否则会漏掉count刚好等于5时还没来得及更新的情况。

第三，全局变量直接使用static声明就行，但不要在递归方法内部重新声明一个同名局部变量，否则你会疯狂怀疑人生。

3.2 Python：全局变量用list包一层更稳

Python的代码量最小，但有两个常见的坑值得提前说。第一个是global的声明问题：如果直接在dfs里给min_diff赋值，必须先声明global min_diff，否则Python会认为你新建了一个局部变量。为了避免这个麻烦，我用一个长度为1的列表min_diff = [total]，闭包里修改min_diff[0]完全不会碰到作用域问题。第二个是输入读取：如果题目输入里恰好只有一行10个数字，用sys.stdin.readline()是可以的；但用sys.stdin.read()统一读进来再split()更稳，这样不管输入是一行还是多行都不会挂。

import sys def main(): data = list(map(int, sys.stdin.read().split())) nums = data[:10] total = sum(nums) min_diff = [total] def dfs(idx, cnt, cur_sum): if cnt == 5: diff = abs(total - 2 * cur_sum) if diff < min_diff[0]: min_diff[0] = diff return if idx == 10: return if 10 - idx < 5 - cnt: return dfs(idx + 1, cnt + 1, cur_sum + nums[idx]) dfs(idx + 1, cnt, cur_sum) dfs(0, 0, 0) print(min_diff[0]) if __name__ == "__main__": main()

这段代码里，我把剪枝、边界、更新答案的顺序固定为：先判断是否选满5人，再判断是否越界，最后判断剩余元素是否够用。这个顺序是有讲究的。如果把剪枝放在最前面，一旦idx正好等于10但count也等于5，答案就永远不会被更新。

Python递归深度在这里只有10层，完全不用担心栈溢出问题。有些人会把这类递归写成迭代，完全没有必要。

3.3 JavaScript：OD机考的JS不是浏览器里的JS

很多前端同学习惯写浏览器里的JavaScript，一到机考环境就懵：没有document，没有window，也没有全局alert。OD机考的JS是Node.js环境，需要自己从标准输入读数据。下面这份代码用process.stdin的data/end事件流，比readline更抗造，不管输入有多少空行、多少连续空格，都能一次解析完。

const process = require('process'); let input = ''; process.stdin.on('data', chunk => { input += chunk; }); process.stdin.on('end', () => { const nums = input.trim().split(/\s+/).map(Number); const total = nums.reduce((acc, cur) => acc + cur, 0); let minDiff = Number.MAX_SAFE_INTEGER; function dfs(idx, count, sum) { if (count === 5) { const diff = Math.abs(total - 2 * sum); if (diff < minDiff) minDiff = diff; return; } if (idx === 10) return; if (10 - idx < 5 - count) return; dfs(idx + 1, count + 1, sum + nums[idx]); dfs(idx + 1, count, sum); } dfs(0, 0, 0); console.log(minDiff); });

这里的关键是split(/\s+/)而不是split(' ')。机考输入里可能出现多个连续空格、制表符、甚至行尾换行，正则\s+能匹配所有空白字符，一次处理干净。Number.MAX_SAFE_INTEGER作为初始最大值也够用，因为这道题的答案不会超过10万。

递归函数定义在事件回调里，通过闭包引用nums、total和minDiff，这是Node.js里很自然的做法。注意别用浏览器里才有的window.Math或者global.parseInt之类的写法，Node.js的全局对象是global，但这里完全用不到。

3.4 C/C++：头文件别偷懒，abs注意类型

C/C++在这道题上优势很明显：代码短、运行快、cin/cout处理10个数毫无压力。但有三个点我见过好几个人翻车。

第一，bits/stdc++.h是GCC的万能头文件，多数在线评测环境支持，但个别严格要求标准头文件的环境会编译失败。建议直接用#include <iostream>、#include <cstdlib>、#include <climits>，不依赖万能头文件更稳。

第二，abs()在C++里对int和long long都有重载。这道题用int没问题，但如果你把total或sum声明成long long，就要用llabs()，否则可能得到错误结果。

第三，ios::sync_with_stdio(false);和cin.tie(nullptr);能加快输入输出，虽然对这道题可有可无，但写上没坏处，还能展示你对性能细节有意识。

#include <iostream> #include <cstdlib> #include <climits> using namespace std; int a[10]; int total = 0; int minDiff = INT_MAX; void dfs(int idx, int cnt, int sum) { if (cnt == 5) { minDiff = min(minDiff, abs(total - 2 * sum)); return; } if (idx == 10) return; if (10 - idx < 5 - cnt) return; dfs(idx + 1, cnt + 1, sum + a[idx]); dfs(idx + 1, cnt, sum); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); for (int i = 0; i < 10; i++) { cin >> a[i]; total += a[i]; } dfs(0, 0, 0); cout << minDiff << endl; return 0; }

INT_MAX来自<climits>，如果你只用<iostream>而忘了这个头文件，在某些环境下会编译报错。全局数组默认初始化为0，这里反正会在main里逐项赋值，所以不用显式初始化。

3.5 Go：没有内置abs，math.Abs要转float

Go的坑比较特殊：标准库里没有int类型的abs函数，只有一个math.Abs，而且入参和返回值都是float64。所以写绝对值时必须写成int(math.Abs(float64(total - 2*sum)))，少一步转换就会编译报错。

输入方面，bufio.Scanner读入一行，然后用strings.Fields按任意空白字符切分，比手动按空格split更健壮，会自动处理多个连续空格。strconv.Atoi的第二个返回值是错误，这里可以忽略，因为机考输入一定是合法整数。

package main import ( "bufio" "fmt" "os" "strconv" "strings" ) var nums []int var total int var minDiff int func dfs(idx, cnt, sum int) { if cnt == 5 { diff := int(math.Abs(float64(total - 2*sum))) if diff < minDiff { minDiff = diff } return } if idx == 10 { return } if 10-idx < 5-cnt { return } dfs(idx+1, cnt+1, sum+nums[idx]) dfs(idx+1, cnt, sum) } func main() { scanner := bufio.NewScanner(os.Stdin) scanner.Scan() parts := strings.Fields(scanner.Text()) nums = make([]int, len(parts)) for i, p := range parts { v, _ := strconv.Atoi(p) nums[i] = v total += v } minDiff = total dfs(0, 0, 0) fmt.Println(minDiff) }

注意这里minDiff初始化为total。因为每个人能力值都是正整数，任何一组5人的和最小也有5，另一组最多total - 5，差值一定小于total。所以用total作为初始最大值是安全的。不要用math.MaxInt32，虽然Go的math包里确实有这些常量，但不同版本和平台下int的位数可能不同，直接用total初始化反而更简单可靠。

bufio.Scanner默认的token大小限制是64KB，本题输入只有一行，远远够用。如果遇到过万的长文本输入，需要调整scanner.Buffer，但这道题完全不需要。

4. 双机位考场上最容易翻车的四个细节

4.1 输入不是你想的那么干净

机考输入看起来是“一行空格分隔”，但实际评测时可能包含换行、多余空格、甚至制表符。如果你用scanner.nextInt()或者cin >> int这种“自动跳过空白”的API，其实没问题；但如果你用readline().split(' ')严格按单个空格切，就可能在多个连续空格或换行时踩坑。

各语言推荐写法：

• Java：Scanner默认用空白符做分隔符，直接nextInt()即可。
• Python：用sys.stdin.read().split()，自动适配任意空白。
• JavaScript：用split(/\s+/)，不要用split(' ')。
• Go：用strings.Fields。
• C/C++：cin >>天然跳过空白。

这几个写法我都有过教训。最早我写JS题时习惯split(' ')，本地测试一切正常，提交后偶发报错，就是因为评测数据里有一个\r字符或者多个连续空格。

4.2 分组不区分先后，别把方案数翻倍

10个人分两组，每组5人。第一组选了{1,2,3,4,5}，另一组自动就是{6,7,8,9,10}。如果你在递归里把“谁进第一组”和“谁进第二组”当成两件事枚举，方案数会翻倍，但最终算出的最小差值还是相同的——因为差值取了绝对值，A组和B组完全对称。翻倍不会导致答案错误，只会浪费一点时间。

真正要小心的是输出。差值取abs(total - 2 * sum)后就是最终答案，不需要再除以2。曾经有人在备考群里问为什么自己的答案是标准答案的两倍，就是拿差值再去做了对称处理，反而搞错了。

4.3 多打印一行调试信息，整题0分

ACM模式严格比对标准输出。很多人在本地IDE跑通了，代码里留着System.out.println("sum=" + sum)或者printf("debug...")之类的调试语句，考场上忘记删。评测系统拿到输出后，发现多了不该有的行，直接判0分。

这个错误离谱但高频。我的习惯是写完代码先自查所有输出语句：凡是System.out.println、print、console.log、fmt.Println、cout，逐行确认是不是最终答案。一条printf只保留最后一行，其他全部删掉。

4.4 样例通过率100%，但实际0分的隐藏原因

还有一种更隐蔽的情况：样例跑通了，提交却是0分。除了调试输出之外，常见原因还有这几类：

• Java类名不是Main，或者写了package声明。
• 文件名和类名不一致，OD平台一般只认Main.java。
• JS代码里用了浏览器API，比如window、document，在Node.js环境根本不存在。
• Go的package不是main，或者缺少func main()入口函数。
• C++代码用了当前编译标准不支持的特性。
• Python代码写在if __name__ == "__main__":外面，导致模块导入时也执行了主逻辑。

这类问题在自己电脑上完全暴露不出来，只有提交到评测机才会出问题。建议考试前先用平台的在线自测功能跑一遍空模板，确认环境正常再开始写题。

5. 从“游戏分组”延伸出去：组合枚举题的通用解法和备考思路

5.1 一套能套用多数组合枚举题的DFS模板

这道题的DFS代码非常典型，可以抽象成一套通用模板：从n个元素里选k个，使某个目标函数最优。核心参数只有两个：当前下标和已选个数。

def dfs(idx, chosen, state): if chosen == k: update_answer(state) return if idx == n: return if n - idx < k - chosen: return dfs(idx + 1, chosen + 1, state + nums[idx]) # 选当前元素 dfs(idx + 1, chosen, state) # 不选当前元素

这套模板可以套到很多100分题上，比如：从n个数里选k个使和最大或最小、判断能否凑出某个目标值、简单子集划分问题。核心就是保证“不重不漏”地遍历所有组合。

我在实际刷题中，会把这道模板题重复写三遍以上，每一遍都默写，直到完全不用思考就能落下每个括号和缩进。考场上心态紧张的时候，肌肉记忆比临场推理可靠得多。

5.2 如果人数不是10而是30，怎么办

这道题固定10人，所以DFS是标准答案。但如果遇到变体，比如n=30选15，C(30,15)超过1.5亿，DFS会直接超时。那时候需要折半枚举的思路：把30个人分成两半，各自枚举所有可能的选中组合和组和，再用哈希表匹配两半的信息，找到最接近total/2的组合。复杂度从组合数级别降到大规模枚举级别。

不过这种进阶思路在OD机考的100分题上一般用不到。200分题如果遇到“两个集合尽量接近”的问题，可以留作备用方案。先把基础模板写对，再考虑优化。

5.3 机考时间分配和语言模板准备

最后聊点实际的备考经验。OD机考的题目结构一般是两道100分题加一道200分题，总时长基本在150分钟左右。我的建议是：

• 前40分钟，先把两道100分题都读一遍，挑最有把握的先做，确保稳定拿到100分。
• 第二道100分题哪怕暂时没思路，也先把暴力解法写出来拿部分分。
• 最后80分钟攻200分题，优先写暴力回溯和简单DP，不要一上来就追求最优解。

语言模板方面，每种语言准备一份“输入输出模板”非常重要。Java就记住Main类和Scanner模板，Python就记住sys.stdin.read().split()模板，JS就记住process.stdin事件流模板，Go就记住bufio.Scanner模板，C++就记住cin >>模板。把这些模板背熟，考试时10秒内能搭出框架，剩下的精力全放在算法上。

如果你正在准备机考，我的建议是：先把你要用的那种语言写熟，再把其他语言版本的差异点过一遍。“游戏分组”是一个极其标准的组合枚举题，它考察的不是算法天赋，而是你在限定时间内把思路稳定落地的能力。把这道题吃透，同类的高频题你都会顺很多。