从一道算法题 探讨深度优先遍历
之前看过这么一道算法题，题目是这样的：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
题目挺简单的，就是 随机给你一个数字类型的数组，nums = [1,2,3]。返回所有全排列：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
看到类似的题目，我们可以用树的思想，将解题过程抽象成树：
说明：
每一个结点表示了求解全排列问题的不同的阶段，这些阶段通过变量的「不同的值」体现，这些变量的不同的值，称之为「状态」；
使用深度优先遍历有「回头」的过程，在「回头」以后， 状态变量需要设置成为和先前一样 ，因此在回到上一层结点的过程中，需要撤销上一次的选择，这个操作称之为「状态重置」；
深度优先遍历，借助系统栈空间，保存所需要的状态变量，在编码中只需要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，path 变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈；
深度优先遍历通过「回溯」操作，实现了全局使用一份状态变量的效果。
使用编程的方法得到全排列，就是在这样的一个树形结构中完成 遍历，从树的根结点到叶子结点形成的路径就是其中一个全排列。
设计状态变量
首先这棵树除了根结点和叶子结点以外，每一个结点做的事情其实是一样的，即：在已经选择了一些数的前提下，在剩下的还没有选择的数中，依次选择一个数，这显然是一个 递归 结构；
递归的终止条件是：一个排列中的数字已经选够了 ，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth，或者命名为 index ，表示当前要确定的是某个全排列中下标为 index 的那个数是多少；
布尔数组 used，初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，这样在考虑下一个位置的时候，就能够以 O(1)O(1) 的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。
这些变量称为「状态变量」，它们表示了在求解一个问题的时候所处的阶段。需要根据问题的场景设计合适的状态变量。
代码实现：
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
int length=nums.length;
boolean [] isxuan=new boolean[length];
List<Integer> tmp=new ArrayList<Integer>();
dfs(nums,0,length,isxuan,tmp,res);
return res;
}
public void dfs(int [] nums,int depth,int legth,boolean [] isxuan,List<Integer> restmp,List<List<Integer>> res){
if (depth==legth){
res.add(new ArrayList<Integer>(restmp));
return;
}
for (int j=0;j<legth;j++){
if (!isxuan[j]){
restmp.add(nums[j]);
isxuan[j]=true;
dfs(nums,depth++,legth,isxuan,restmp,res);
isxuan[j]=false;
restmp.remove(restmp.size()-1);
}
}
}