一.题目描述

输入一个数n，输出1~n的全排列。

二.解题思路

我们可以先把问题形象化，举个例子，我们有1，2，3个箱子和号数为 1，2，3的三张扑克，放到箱子有几种放法？第一步就是先将1号扑克放到1号箱子里，然后把2号扑克放到2号箱子里。

以此类推，直到当我们到第四个箱子面前（好像没有第四个箱子(/ω＼)），因为我们不需要第四个箱子，所以此时已经完成了一次排列。

那么接下来，我们回到第3号箱子（递归），把扑克收回，此时扑克3号在我们手中（标记），再次回到第2号箱子这里，将2号扑克收回，此时2号扑克在我们手中，我们继续遍历放置，再将3号扑克放到2号箱子里，然后走到了3号箱子，把2号扑克放到3号箱子里，此时又完成了一次排列组合。按照这个步骤模拟，就会得出排列。

123
132
213
231
312
321

那么此时程序应该怎么实现呢？

#include<stdio.h>

int box[10],joker[10],n;

void dfs(int step) //step表示现在站在第几个盒子面前
{
    int i;
    if (step == n+1) //如果站在第n+1个盒子面前，则表示前n个盒子已经放好了扑克牌
    {
        //输出一种排列（1~n号盒子中的扑克牌序号）
        for ( i = 1; i <=n; i++)
        {
            printf("%d",box[i]);
        }
        printf("\n");   

        return; //返回之前的一步（最近一次调用dfs函数的地方)
    }
    //此时站在第step个盒子面前，应该放哪张牌呢？
    //按照1,2,3....n的顺序一一尝试
    for ( int j = 1; j <=n; j++)
    {
        //判断扑克牌i是否还在手上
        if (joker[j] == 0) //book[i]等于0表示i号扑克牌在手上
        {
            //开始尝试使用扑克牌i
            box[step] = j; //将i号扑克牌放入到第step个盒子中
            joker[j] = 1; //将Book[i]设为1,表示i号扑克牌已经不再手上
            //第step个盒子已经放好扑克牌，接下来需要走到下一个盒子面前
            dfs(step+1); //这里通过函数的递归调用来实现（自己调用自己）
            joker[j] = 0; //这是非常重要的一步，一将要将刚刚尝试的扑克牌收回，才能进行下一次尝试
        }        
    }
    return;
}
int main()
{
    scanf("%d",&n); //输入的时候323注意n为1~9之间的整数
    dfs(1); //首先站在1号小盒子3面前
    getchar(); getchar();
    return 0;
}

这个简单的例子（恶心了我两天），核心代码很短，但是却饱含了深度优先搜索（Depth First Search）DFS的基本模型，理解DFS的关键在于：“当下该如何做”，至于“下一步应该怎么做”则与“当下应该怎么做”一样的，比如我们这里写的dfs函数主要功能是解决当你在第step个盒子的时候你该怎么办。通常的方法是把每一种可能都去尝试一遍（for循环），当这一步成功解决后进入下一步（step+1）。

即：

//判断边界

for(i = 1;i<=n;i++)//尝试每一种可能

{

 dfs(step+1)  //继续下一步

}

每一种尝试就是一种“扩展”，每次站在一个盒子面前的时候，都有n（n表示全排列的n）种扩展方法，但并不是每种扩展都能成功。

到这里这题就结束了，简单的题目描述，饱含了一种算法模型，希望早点能吸收消化。。