啊哈算法——全排列

题目链接

全排列

描述：

输入一个自然数N（1<=N<=9），从小到大输出用1~N组成的所有排列，也就说全排列。例如输入3则输出
123
132
213
231
312
321

输入格式：

输入一个自然数N（1<=N<=9）

输出格式：

N的全排列，每行一个

输入样例：

3

输出样例：

123
132
213
231
312
321

代码：

#include<bits/stdc++.h>
using namespace std;
int a[10],book[10],n;//全局变量在不赋值之前默认是零 
void dfs(int step){//step表示站在第几个盒子前面 
    int i;
    if(step==n+1){//如果站在第n+1个盒子前，代表之前的盒子都装满了 
        for(i=1;i<=n;i++){
            printf("%d",a[i]);//输出一种排列 
        }
        printf("\n");
        return;//结束这次递归，并返回最近一次调用 
    }
    for(i=1;i<=n;i++){
        if(book[i]==0){//表示扑克牌在手上 
            a[step] = i;//将第i个扑克牌放到第step个盒子里 
            book[i] = 1;//表示扑克牌已经不再手上 
            dfs(step+1);//走到下一个盒子前 
            book[i] = 0;
            //将之前的扑克牌收回，表示前面的盒子所有可能性已经全部结束 
        }
    }
    return;
}
int main(){
    scanf("%d",&n);
    dfs(1);//站在一号盒子前 
    return 0;
}

解析：

利用DFS(深度优先搜索)，每次调用自己，并判断几号扑克牌在手中，那个盒子是空着的。最后将其放入盒子中。