把 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
思路
用dfs深度优先搜索来做，以给的例子为例，先划出三个位置，然后对于第一个位置，可填的数有1、2、3，也就有三个分支，然后再去每个分支进行第二个位置的填数，然后是第三个。
这里注意：数只能用一次，所以就需要对于数字进行标记是否用过。
对于字典序最小，实际上只要按照顺序来做就行了
#include<iostream> #include<cstdio> using namespace std; const int N = 10; //这里注意全局数组会自动赋值为0、false int n; bool used[N]; //用没用过 int state[N]; //表示放的是哪个数，0：还没放 void dfs(int u) { //先判断边界 if(u > n) { //直接打印方案 for(int i = 1 ; i <= n ; i ++) printf("%d ", state[i]); puts(""); //puts表示输出“字符串+换行” } for(int i = 1; i <= n; i ++) if(!used[i]) // 如果i没有用过 { state[u] = i; used[i] = true; dfs(u + 1); //恢复现场 state[u] = 0; used[i] = false; } } int main() { cin >> n; dfs(1); //从哪个数字开始搜索 return 0; }
