假设开始为1，第二个位置有2和3两个数供选择，如果第2个数选择3，那么第3个数只能选2.返回第二步则可以选择2，又生成另一种排序。之前acm社团讲题时提到过这个算法，但没有代码演示，遂没有深究。但只对三个数进行全排列，用3个for循环也可以解决。代码如下：

如果对4个数呢，4个for循环，对n个数呢？显然不行。

基于开头的思想，一条路走到黑到死胡同了，然后返回一步，再看看有没有其他路口，不行再退一步.....

先给出1~n（n<9)的全排类代码吧，边看边分析（其实我也不太熟悉，初学）

就用n=3来举例。从main函数进入dfs函数，此时step=1，表示第一步。具体作用表示在于排列元素的标号，因为后面会有a[step]=i给排列列表赋值。此时book数组元素全为0，开始搜索。i=1，先判断book[i]是否等于0，此时进入赋值部分：a[1]=1，book[1]=1。接着递归dfs（step+1）对第二个元素处理，即找第一个元素的分支。此时book[i]！=0，退出循环，i++。i==2，同上a[2]=2,book[2]=1.继续推则有

a[1]=1,a[2]=2,a[3]=3 .此时n=4，输出序列1 2 3.book[3]=0(路走到尽头了），i=3,不再进入循环，回到第二层搜索，book[2]=0，再次判断，book[i]=0 (i==3),于是a[2]=3,book[3]=1,再次进入下一层搜索搜索a[3]=2,book[2]=1,得到序列1 3 2.（有点绕晕了，越讲自己越迷糊。）

来自网上搜到的dfs模板