递归实现排列型枚举

链接：https://ac.nowcoder.com/acm/contest/998/C
来源：牛客网
题目描述
把 1\sim n1∼n 这 n(n \lt 10)(n<10)个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入描述:
一个整数n。
输出描述:
按照从小到大的顺序输出所有方案，每行1个。 首先，同一行相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
解题思路：从1开始搜索并标记，每次搜索每个数有没有用到，没用到就保存并标记，每当搜索完所有数时输出并返回，撤销标记

#include<iostream> 
using namespace std;
int n;
int ans[10];//保存当前的方案
int use[10];//表示每个数是否被用过
void dfs(int x) {//X表示当前搜索到那个数
    if (x > n) {//如果N位都搜索完了，就输出方案并返回
        for (int i = 1; i <= n; i++) {
            cout << ans[i] << ' ';//输出方案 
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {//从小到大枚举
        if (!use[i]) {//判断这个数是否用过
            ans[x] = i;//保存到方案中 
            use[i] = 1;//标记这个数被使用了
            dfs(x + 1);//进行下一步搜索
            use[i] = 0;//撤销标记
        }
    }
}
int main() {
    cin>>n;//输入
    dfs(1);//从第一个数开始搜索；
    return 0;
}