递归实现排列型枚举

把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式
一个整数n。

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

输入样例：

3

输出样例：

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

打印出全部的结果，依然用n=3来举例，挨个位置来看能有那些可供选择的数字，搜索出全部结果，画出搜索树如下

一开始看第一个位置，这个位置有三个选择：1,2,3然后深度优先，选择1之后看第二个位置有两个选择，最后剩一个选择到达边界之后进行输出
代码如下

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 9;

int n;
int st[N]; //0是未定，否则是几就放几 状态数组，放的就是最后的结果
bool used[N]; //true：用过了  false：没用过

void dfs(int u)
{
    if(u == n){   //判断边界 到了边界了就开始打印状态数组里面的东西
        for(int i = 0 ; i < n ; i++)
            printf("%d ", st[i]);
        puts("");
        return;
    }

    //还没有到边界，即当前位置还是需要放数字的，那么开始遍历一边used数组，看看那个没用过
    for(int i = 0 ; i < n ; i ++){
        if(!used[i]){
            st[u] = i+1;
            used[i] = true;
            dfs(u+1);

            //没用过的就放上这个数字，然后看下一个位置可以放那些数（即走一遍dfs）
            //完成回来还要判断这个位置能不能放别的数字，即走另一个分支，开始走之前要恢复现场
            st[u] = 0;
            used[i] = false;
        }
    }
}

int main()
{
    cin >> n;

    dfs(0);

    return 0;
}

注：解释下代码中的边界判断，这是递归函数中首先要思考的东西，是重要的判断条件，这里u代表要选择的位置，而每次填完一个位置之后就要让u指向下一个位置，我们依然用的是数组下标，下标==n的时候即已经超出了数组的所划定的范围，就要开始进行输出，这里用了puts("")输出空字符串后面就会天然的带一个换行
注：题目要求按照字典序输出，在写代码的时候每一个分支的判断就是按照字典序从小到大的顺序来搜索，所以最后的结果就一定是字典序，不用在加以特殊的判断
(字典序：p,q两个序列，从第一项开始比较，如果相同就开始比较下一项，当前项较小的字典序就是小，若有一个为空了，那么他的字典序小于另一个)