牛客-998A 递归实现指数型枚举（递归）¶

牛客-998A 递归实现指数型枚举（递归）¶

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

题目描述¶

从 $1\sim n$ 这 $n (n \leq 16)$ 个整数中随机选取任意多个，输出所有可能的选择方案。

输入描述:¶

一个整数n。

输出描述:¶

每行一种方案。同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

示例1

输入¶

输出¶

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

using namespace std;

int n;
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 (x == n + 1) {
        cout << 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;
    calculate(1);

    return 0;
}

递归的入门题，来源于《算法竞赛进阶指南》的递推与递归章节。