公平抽签
题目描述
小A的学校，蓝桥杯的参赛名额非常有限，只有 m 个名额，但是共有 n 个人报名。
作为老师非常苦恼，他不知道该让谁去，他在寻求一个绝对公平的方式。
于是他准备让大家抽签决定，即 m 个签是去，剩下的是不去。
小 A 非常想弄明白最后的抽签结果会有多少种不同到情况，请你设计一个程序帮帮小 A！
输入描述
输入第一行包含两个字符 n,m，其含义如题所述。
接下来第二行到第 n+1 行每行包含一个字符串 S ，表示个人名。
1≤m≤n≤15。
输出描述
输出共若干行，每行包含 m 个字符串，表示该结果被选中到人名（需按字符串的输入顺序大小对结果进行排序）。
输入输出样例
示例
3 2
xiaowang
xiaoA
xiaoli
xiaowang xiaoA
xiaowang xiaoli
xiaoA xiaoli
回溯算法
这段代码实现了一个经典的回溯算法，用来解决组合问题。在这个问题中，我们要从n个人中选出m个人参加比赛。下面是注释过的代码：
#include <iostream>
#include <vector>
using namespace std;
// n 表示总人数，m 表示需要选择的人数
int n, m;
vector<string> path; // 存储当前组合的路径
vector<int> used; // 标记某个人是否已被选中
// 回溯算法主体函数
// s 是参与抽签的所有人的名单
// start 是开始选择的起点索引，防止重复组合
void backtracking(const vector<string>& s, int start) {
// 如果当前路径的长度等于所需人数，就输出这个组合
if (path.size() == m) {
for (int i = 0; i < m; i++) // 输出当前组合
cout << path[i] << " ";
cout << endl; // 换行，为输出下一个组合做准备
return; // 返回上一层
}
// 从start开始尝试每个可能的选项
for (int i = start; i < s.size(); i++) {
if (used[i] == 0) { // 如果当前人未被选中
used[i] = 1; // 标记为已选中
path.push_back(s[i]); // 将此人加入当前路径
backtracking(s, i + 1); // 递归，注意下一次选择从i+1开始，避免重复
used[i] = 0; // 回溯，撤销选择
path.pop_back(); // 从当前路径移除此人
}
}
}
int main() {
cin >> n >> m; // 输入总人数和需要选择的人数
vector<string> s(n); // 创建一个大小为n的字符串数组s，存储人名
used.resize(n, 0); // 调整used的大小与人数相匹配，并全部初始化为0
// 读入所有人的名单
for (int i = 0; i < n; i++)
cin >> s[i];
backtracking(s, 0); // 从第一个人开始递归回溯搜索所有组合
return 0; // 程序结束
}
这段代码的核心是对回溯算法的实现。它使用backtracking函数递归地创建所有可能的m个人的组合，并在找到一个有效组合时打印它。通过start参数和used数组来排除重复的组合和避免选择已经被选中的人。当路径path的大小达到m时，当前路径代表了一个有效的组合，代码会将其打印出来，然后返回上一层继续寻找其他可能的组合。