把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 n。
输出格式
按照从小到大的顺序输出所有方案，每行 11 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围
1≤n≤9
输入样例：
3
输出样例：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N = 10; int n; int state[10]; //0表示还没有放数 1~n表示放了哪个数 int used[10]; //1表示用过 void dfs(int u) { if ( u > n ) //边界 { for (int i = 1; i <= n; i++) { printf("%d ", state[i]); } puts(""); return; } //依次枚举每个分支，即当前位置可以填哪些数 for (int i = 1; i <= n; i++) { if (used[i]==0) //如果还没有用过 { state[u] = i; used[i] = 1; dfs(u + 1); //恢复现场 state[u] = 0; used[i] = 0; } } } int main() { scanf("%d", &n); dfs(1); return 0; }
