话不多说，上代码

嘛，还是先说说我们面对的问题吧 （帅不过一秒的我）

问题其实很简单，输入一个数字n（范围1~9），然后求1～n的全排列。比如n=3，我们就要求123的全排列。高中的数学课也有全排列的问题，但一般不会让你一一列出就是了。

今个儿就用一种不撞南墙不回头的算法——深度优先算法来解决这个问题。

上代码

别急，咱先说说解决问题的思路（放下刀子，咱还是盆友）

就拿123的全排列来举个栗子。我们有分别标着1,2,3的三盒子以及分别标着1,2,3的三张牌。每个盒子只放一张牌，从盒1开始放，放牌顺序是先牌1，再2，最后3。所以，先把牌1放到盒1，接着把牌2放到盒2，接着把牌3放到盒3，一种排列出来了—— 123 ，我们不是要求全排列么，对，所以还没完，把牌3从盒3中拿出，我们想把另一张牌放入盒3然而并没有，只好去盒2，把牌2拿出，此时我们有两张牌，我们按照约定的顺序把牌3放进去（之前是牌2，所以现在到3），然后去到盒3把仅有的一张牌2放入——132就出来了，继续继续，把牌2从盒3拿出，去盒2，把牌3拿出（之前是3，所以现在放1，但没有），只好去盒1，把牌1拿出，按照约定的顺序把牌2放入，去盒2，把牌1放入，去盒3，把牌3放入——213出来了……以此类推，可以把231,312,321也求出来。

代码

#include <stdio.h>

int a[10],book[10],n; //用a[]表示盒子，book[]来记录手上有没有某张牌

void dfs(int step)
{
    int i;
    if(step == n + 1)
    {
        for(i = 1; i <= n; i++)
            printf("%d",a[i] );
        printf("\n");

        return;
    }

    //此时站在第step个盒子面前
    for(i = 1; i <= n; i++)
    {
        if(book[i] == 0)  //牌i在手上的意思
        {
            a[step] = i;
            book[i] = 1; //牌已不在手上
            dfs(step + 1); //骚气的开始
            book[i] = 0; //将刚才尝试的牌收回，进行下一次尝试
        }
    }
    return;
}

int main()
{
    scanf("%d",&n);
    dfs(1);
    getchar();getchar();
    return 0;
}

跟着代码走走

字丑加相机渣

吐槽

这玩意到底怎么想出来的
啊哈磊！你的书不给代码下载，我打字很累诶