深搜－－全排列

[题 目]

输入一个数n，输出1~n的全排列。 举例：假如有编号为1 2 3的3张扑克牌和编号为1 2 3 
的3个盒子里，并且每个盒子有且只能放一张扑克牌。那么一共有多少种不同的放法呢

[分 析]

当小哼走到第四个盒子的时候，已经完成一种排列。产生一种排列之后小哼需要立即返回。小哼需要退一步重新回到3号盒子前面，取回放在3号盒子的扑克牌，再往3号盒子放牌时已没有别的选择，于是再回退一步，回到2号盒子面前，收回2号牌。现在需要往2号盒子放3号牌，再把仅剩的2号牌放入3号盒子，又来到4号盒子，产生新排列132，按此步骤模拟，会依次产生所有排列213 231 312 321 

[代  码]

#include<iostream>  

#include<string>  

#include<cstdio>

using namespace std;  

int a[10],book[10],n;

void dfs(int step)//step表示站在第几个盒子面前

{int i;

if(step==n+1) //如果站在第n+1个盒子面前，则表示前n个盒子已经放好扑克牌

{//输出一种排列（1－n个盒子中的扑克牌）

for(i=1;i<=n;i++)

cout<<a[i]<<" ";

cout<<endl;

return;// 返回之前的一步 （最近一次调用dfs函数的地方）  回溯

} 

 

for(i=1;i<=n;i++)

{//判断扑克牌i是否还在手中

if (book[i]==0)

{a[step]=i;//将i号扑克牌放入到第step个盒子中

book[i]=1;//将book[i]设为1,表示i号扑克牌已经不在手上

//第step个盒子已经放好扑克牌，接下来需要走到下一个盒子面前

dfs(step+1);

book[i]=0;//这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试

} 

}

return;

} 

int main()

{cin>>n;//输入的时候要注意n为1－9之间的整数

dfs(1); //首先站在1号小盒子面前

return 0; 

}