题目描述

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

输入格式
输入一个整数n。

输出格式
每行输出一种方案。

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

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

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

数据范围
1≤n≤15
输入样例：
3
输出样例：

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

参考文献

本模板来自秦大佬https://www.acwing.com/solution/acwing/content/799/
还有这位不知名的大佬 https://www.acwing.com/problem/content/solution/94/1/
发这篇很low的博客的原因是我学习了他们的思想后终于算是自己仿照着写了一篇，对于递归终于算是有点入门了
思想就是萝卜填坑
个人感觉深度优先遍历就是一条路走到黑，到了终点后开始返回（回溯），回到分叉点后，假如又存在路，继续走到终点，。。。直到无路可走（或者说路全部走完了），结束，不知道思想对不对，求大佬指正，谢谢

C++ 代码

#include<iostream>

using namespace std;

int q[10];//这个数组存储要排列的数
bool vis[10];//判断每个数是不是被访问过
int n;

void dfs(int u)
{
    if(u==n+1)//枚举到第n+1个坑，说明坑已经填完了
    {
        for(int i=1;i<=n;i++)
        cout<<q[i]<<' ';
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=true;//这个数被访问过
            q[u]=i;//当前枚举的坑存的数值为i;
            dfs(u+1);//枚举下一个坑
            q[u]=0;//恢复现场
            vis[i]=false;//同上
        }
    }
}

int main()
{
    cin>>n;
    dfs(1);
}
blablabla