《算法笔记》8.1小节——搜索专题->深度优先搜索（DFS）之[递归入门]全排列

题目描述 排列与组合是常用的数学方法。
先给一个正整数 ( 1 < = n < = 10 )
例如n＝3，所有组合,并且按字典序输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
输入输入一个整数n( 1<=n<=10)输出输出所有全排列
每个全排列一行，相邻两个数用空格隔开（最后一个数后面没有空格）样例输入
3
样例输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
题目链接：
codeup.cn/problem.php?cid=100000608&pid=0
解题思路：
假如有编号为1 、2、3 的3 张扑克牌和编号为l 、2 、3 的3 个盒子。
现在需要将这3 张扑克牌分别放到3 个盒子里面，并且每个盒子有且只能放一张扑克牌。那么一共有多少种不同的放法呢？
首先 我们应该设置一个标志数组 book 记录当前数字的扑克牌是否被使用过。0表示未使用，1表示已经使用了。 然后用一个数组a 表示盒子并且初始化a[i]=i。
设计递归：
递归边界——step等于n+1，即n个盒子里面全部装满了数字，然后打印这一组盒子里的数字即可。递归主体——第step个盒子放编号为i的数字，然后将该编号i的数字标记为1，用来表示该数字已经使用。然后再第step+1的盒子里放数字，使用过的数字不能再使用，使用未使用过的数字，如此递归下去，直到到达边界即可。最终将标记过的数字回溯，即类似迷宫的岔路口，到达某一死胡同后，返回到最初的岔路口，进行下一种走法，即下一种全排列。
代码如下：

#include<stdio.h>
int n,a[10],book[10];//特别说明c语言全局变量没有赋值默认为 0,无需再次初始化；
void dfs(int step)//step 表示当前在第几个位置
{ int i; 
    if(step==n+1)//如果step==n+1表示前n个数字已经放好
    {  //输出一种全排列
        for(i=1;i<=n;i++)
        {
            if(i==n) printf("%d\n",a[i]);
            else printf("%d ",a[i]);
        }
    return;
    }
    
    for(i=1;i<=n;i++)//每次搜索都从1-n 一一尝试
    {
        if(book[i]==0)//判断次数字是否用过
        {
            a[step]=i;//存储当前位置的数字，以便满足条件输出
            book[i]=1;//当前数字已用过，改变标志，以防重用
            dfs(step+1);//放好当前位置数字之后，安排下一个数字
            book[i]=0;//回溯，当满足一种全排列后，进行下一种尝试
        }
    }
    return ;
}
int main()
{ 
    scanf("%d",&n);//输入只能为1-9之间的整数，表示1-n的全排列
    dfs(1);//从第一个位置开始
    return 0;
} 

补充：
对于本题其实就是利用深度优先搜索进行解题的，每一种全排列可看成迷宫的一条死底胡同路径，到达死胡同底，然后再返回到最初的岔路口，再进行下一次深度探索，最终达到迷宫的出口。
对于递归的算法代码理解，画出递归树即可，也要注意回溯。设计递归，要知道递归边界，递归公式（即递归的主要思想）（设计递归就是多看大神的代码，跟数学一样，越菜越爱玩，久而久之自己也变成更强的菜鸟了（滑稽））。