第一节：深度优先搜索
描述：输入一个数字m，输出1-m的全排列。
首先思考：假如有编号为1,2,3的三张扑克牌和编号为1,2,3的3个盒子，现在需要将这3张扑克牌分别放在3个盒子中有几种不同的方法。
步骤：首先走到1号盒子面前，是先放1号牌还是2号牌还是3号牌？现在要生成的是全排列，显然都要去尝试，现在规定一个顺序，每次到了一个盒子的面前，都先放1号，再放2号，最后放3号。
首先走到1号盒子面前，先放1号牌放到1号盒子中，到2号盒子面前放2号牌，到3号盒子面前放3号牌。假如还有一个盒子叫做4号盒子，其实不需要这个4号盒子，因为放过3号盒子的3号牌，已经生成了一个排列。
这个顺序就是“1，2，3”。
是不是结束了，肯定不是了，拿你的脚指头想一下1，2，3这三个数字的全排列肯定不是一种。那我该怎么去想啊。
策略：产生一种全排列之后需要立即返回，退回到3号盒子面前，取回3好盒子中的扑克牌，再去尝试看看能不能放下其他号码的扑克牌，这个不用想，你手里只有一张3号的牌肯定没有其他的牌了，于是再退回一步，回到2号盒子面前
取出2号盒子中的扑克牌，现在手里已经有了两张牌分别是2号和3号扑克牌，需要往2号盒子中放3号扑克牌，到3号盒子面前把手中的2号牌放进去，就又产生了一种排列“1，3，2”。
好了啰嗦了一大会不知道大家听懂没有，下面上代码：
package 中介者设计模式;
import java.util.Scanner;
public class Main {
static int [] a = new int[10];
static int [] flag= new int [10];
static int n = 0;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("输入一个正整数");
n = input.nextInt();
dfs(1);//首先站在1号盒子的面前
}
/**
*
* @param step 表示站在第几个盒子的面前
*/
private static void dfs(int step) {
if (step == n+1) {//站在第n+1个盒子面前说明前面的盒子已经产生出来一种全排列了，大家应该知道这个4是干什么的了把
//输出一种全排列
for (int i=1;i<=n;i++) {
System.out.print(a[i]);
if (i != n) {
System.out.print(",");
}
}
System.out.println();
return ;//这个return不能忘记了，返回调用的上一步
}
//站在第step的盒子面前怎么放那？
//按照1，2，3顺序依次尝试这个就是我们定义的规则
for (int i=1;i<=n;i++) {
//判断i号扑克牌在手上没有
if (flag[i] == 0) {//标识i号牌在手上
//开始尝试i
a[step] = i;//将i号扑克牌放到step号盒子中
flag[i] = 1;//不在手上了
//第step盒子已经放好了，需要走到下一个盒子面前
dfs(step+1);
flag[i] = 0;//这个就是退回收回扑克的操作。
}
}
}
}