我的github地址：leetcode
给定一个 没有重复 数字的序列，返回其所有可能的全排列。 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]思想：找一个数组的全排列，肯定是回溯算法了，搜索一般就是dfs “回溯”指的是“状态重置”，可以理解为“回到过去”、“恢复现场”，是在编码的过程中，是为了节约空间而使用的一种技巧。而回溯其实是“深度优先遍历”特有的一种现象。之所以是“深度优先遍历”，是因为我们要解决的问题通常是在一棵树上完成的，在这棵树上搜索需要的答案，一般使用深度优先遍历。
以数组 [1, 2, 3] 的全排列为例。
我们先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]； 再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]； 最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]。应该怎么做呢 我们只需要按顺序枚举每一位可能出现的情况，已经选择的数字在接下来要确定的数字中不能出现。按照这种策略选取就能够做到不重不漏，把可能的全排列都枚举出来。
在枚举第一位的时候，有 3 种情况。 在枚举第二位的时候，前面已经出现过的数字就不能再被选取了； 在枚举第三位的时候，前面 2 个已经选择过的数字就不能再被选取了。1、首先这棵树除了根结点和叶子结点以外，每一个结点做的事情其实是一样的，即在已经选了一些数的前提，我们需要在剩下还没有选择的数中按照顺序依次选择一个数，这显然是一个递归结构；
2、递归的终止条件是，数已经选够了，因此我们需要一个变量来表示当前递归到第几层，我们把这个变量叫做 depth；
3、这些结点实际上表示了搜索（查找）全排列问题的不同阶段，为了区分这些不同阶段，我们就需要一些变量来记录为了得到一个全排列，程序进行到哪一步了，在这里我们需要两个变量：
（1）已经选了哪些数，到叶子结点时候，这些已经选择的数就构成了一个全排列； （2）一个布尔数组 used，初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，这样在考虑下一个位置的时候，就能够以 O(1)O(1)O(1) 的时间复杂度判断这个数是否被选择过，这是一种“以空间换时间”的思想。
我们把这两个变量称之为“状态变量”，它们表示了我们在求解一个问题的时候所处的阶段。
4、在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
5、另外，因为是执行深度优先遍历，从较深层的结点返回到较浅层结点的时候，需要做“状态重置”，即“回到过去”、“恢复现场”，我们举一个例子。
从 [1, 2, 3] 到 [1, 3, 2] ，深度优先遍历是这样做的，从 [1, 2, 3] 回到 [1, 2] 的时候，需要撤销刚刚已经选择的数 3，因为在这一层只有一个数 3 我们已经尝试过了，因此程序回到上一层，需要撤销对 2 的选择，好让后面的程序知道，选择 3 了以后还能够选择 2。
这种在遍历的过程中，从深层结点回到浅层结点的过程中所做的操作就叫“回溯”。
static List<List<Integer>> res = new ArrayList<>(); public static List<List<Integer>> permute(int[] nums) { List<Integer> list = new ArrayList<>(); if(nums.length==0||nums==null){ return res; } permuteSort(0,list,nums.length,nums); return res; } public static void permuteSort(int s,List<Integer> list,int len,int[] nums){ if(s==len) { res.add(new ArrayList<>(list)); } for(int i=s;i<len;i++){ swap(nums,s,i); list.add(nums[s]); permuteSort(s+1,list,len,nums); list.remove(list.size()-1); swap(nums,s,i); } } public static void swap(int[] nums,int a,int b){ int t =nums[a]; nums[a] = nums[b]; nums[b] = t; }在递归的终止条件那块写的是 res.add(new ArrayList<>(list)); 这涉及到java的参数传递知识，如果参数是基本类型，他传递的是值，这个值的改变不会影响原变量，但传递的是一个对象的话，传递的是这个对象的地址，这样当回溯的时候，list会进行remove操作，此时，res中的list会随之remove这样会返回空的结果集。 看不懂的话大家可以debug一下，这样会更清楚明了。
