0 题目来源

acwing

1 涉及到的知识点

递归
本题为指数型枚举的递归，代码较为简洁，注意不要只顾着使用for循环对1~n进行枚举，而忘记了递归本身也具有枚举的功能。
本题的关键在于实现对每个数分支递归的功能。

2 题目描述

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

3 输入输出

输入：
输入一个整数n。

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

4 数据范围

1≤n≤15

5 样例

输入样例：
3
输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

6 思路

本题要求在1~n中随机选取任意多个，因此对于每个数来说，只有选/不选两种情况。我们只需要遍历1~n，递归对1~n所有数的这两种情况进行遍历即可。
设置一个递归函数f(int num)，num为当前正在处理的数。
由于需要依次对1~n的数进行处理，因此该函数的退出条件为num==n，即当处理完第n个数后，则代表所有数都已经处理完毕，需打印输出结果，返回上一层。
对于每一个数，都有两种情况，不选/选（见注释）。如果不选，则arr数组的对应位置为0，不需改变，直接进入下一个数的处理；如果选，则将arr数组的对应位置置1，表示选择该数。注意：在完成选择部分的递归后，需要再次把对应位的arr数组置0，等待下次的选择（恢复现场）。

7 代码

#include<iostream>
using namespace std;
int n;
int arr[16];
void f(int num)
{
    if(num==n)//退出
    {
        for(int i=0;i<n;i++)//打印这种情况
        {
            if(arr[i])
                cout<<i+1<<' ';
        }
        cout<<endl;
        return;
    }
    //不选该数
    f(num+1);
    //选择该数
    arr[num]=1;
    f(num+1);
    arr[num]=0;
}
int main()
{
    cin>>n;
    f(0);
    return 0;
}