【例82.3】 公平抽签

解题思路

按输入编号递增选择m人。DFS记录已经选择的编号，每层只从上一次编号之后继续选；选满m人则按选择顺序输出名字。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

是组合不是排列，同一组人不因顺序不同重复输出。

复杂度

输出C(n,m)组，时间O(m·C(n,m))加名字输出，辅助O(n+m)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> name(n);
    for (auto &s : name)
        cin >> s;
    vector<int> chosen;
    function<void(int)> dfs = [&](int start) {
        if (int(chosen.size()) == m) {
            for (int i = 0; i < m; i++) {
                if (i)
                    cout << " ";
                cout << name[chosen[i]];
            }
            cout << "\n";
            return;
        }
        int need = m - chosen.size();
        for (int i = start; i <= n - need; i++) {
            chosen.push_back(i);
            dfs(i + 1);
            chosen.pop_back();
        }
    };
    dfs(0);
    return 0;
}