[C++知识库]NC50919-递归实现排列型枚举

递归实现排列型枚举

题号：NC50919
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述?

把?1～n1～n?这 n(n<10)(n<10)个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入描述:

一个整数n。

输出描述:

按照从小到大的顺序输出所有方案，每行1个。 首先，同一行相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

示例1

输入

复制

3

输出

复制

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

//#include <bits/stdc++.h>
#define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<iostream>
typedef long long ll;
 
using namespace std;
const int maxn = 300005;
const int inf = 1e9+7;
int n;
int a[10];
bool st[11];
void dfs(int x){
    if(x==n){
        for(int i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            a[x]=i;
            st[i]=true;
            dfs(x+1);
            st[i]=false;
        }
    }
    
}
int main(){
    cin>>n;
    dfs(0);
    return 0;

}