牛客-998B 递归实现组合型枚举(递归)

https://ac.nowcoder.com/acm/contest/998/B

题目描述

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。$n> 0, 0 \leq m \leq n, n + (n - m) \leq 25$

输入描述:

两个整数n，m。

输出描述:

按照从小到大的顺序输出所有方案，每行1个。首先，同一行内的数升序排列，相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 9 12排在1 3 10 11前面）。

示例1

输入

5 3

输出

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

---

#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int n, m;
set<vector<int>> s;
vector<int> res;

ostream & operator<<(ostream & os, const vector<int> & v)
{
    for (auto e : v) os << e << " ";
    os << endl;

    return os;
}

void calculate(int x)
{
    if (res.size() > m || res.size() + n - x + 1 < m)
        return;

    if (x == n + 1) {
        s.emplace(res);
        return;
    }

    //不选择
    calculate(x + 1);
    res.push_back(x); //选择x
    calculate(x + 1);
    res.pop_back(); //恢复原状
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    calculate(1);
    for (const auto & e : s)
        cout << e;

    return 0;
}

相比较递归实现指数型枚举，这里多了剪枝，即如果当前选择的数量超过了m，或者剩下的所有数据都选也无法达到m，那么就应该及时返回，避免无用的搜索。