题目描述

从 1∼n 这 n

个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n

。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1

个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

$1\leq n\leq 15$

算法

(递归+STL vector) $O(?)$

自认为写的比较简洁。 直到遇到了y总
当前状态有三个分支：

1.不选择当前数字

2.选择当前数字

3.已经枚举到 $n$ 个数字了，可以输出方案并且返回了

C++ 代码

//2021/6/3

#include <cstdio>

#include <vector>

using namespace std;

int n;

vector<int>chosen;

inline void clac(int x)
{
    if(x==n+1)//如果目前枚举到的数已经是 n+1 了，那说明超过了，可以结束了
              //于是输出当前方案。
    {
        for(register int i=0;i<chosen.size();i++)
        {
            printf("%d ",chosen[i]);
        }

        /*
        C++11新特性:auto
        比较推荐C++同学写这种写法，比较简洁并且十分容易检查
        但是不知道NOI系列赛事支不支持C++11
        for(auto i:chosen)
        {
            printf("%d ",i);
        }
        */

        printf("\n");

        return;
    }

    //如果不选择 x 这个数，那么直接开始枚举 x+1 
    clac(x+1);

    //如果选择 x 这个数 
    chosen.push_back(x);

    clac(x+1);

    chosen.pop_back(); //还原现场 
}

int main(void)
{
    scanf("%d",&n);

    clac(1);//从 1 开始枚举

    return 0;
}