給定一個沒有重復數字的序列，返回其所有可能的全排列。
示例:
輸入: [1,2,3] 輸出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]
?
參考博客：https://blog.csdn.net/summerxiachen/article/details/60579623
思路： 舉例 1 2 3 4?
leetcode 快速排序？1.回想自己大腦里面對1234的全排列的情況。首先固定1，然后對2 3 4進行分類，也就是固定第二個數字，2? 。再往下，就是{1，2} 對3 4進行選擇。固定3，排列為 1，2，3，4
固定4，排列為1，2，4，3。
因此我們可以回想到我們對全排列的思路是： 先固定第一個數，剩下的數字進行全排列。比如1，2，3，4固定1之后，就是對2，3，4進行全排列。固定2之后，就是對3，4全排列。
?
對
T=【T=【x1,x1,x2,x3,x4,x5,........xn?1,xn】x2,x3,x4,x5,........xn?1,xn】
回溯算法詳解，我們獲得了在第一個位置上的所有情況之后(注：是所有的情況)，對每一種情況，抽去序列TT中的第一個位置，那么對于剩下的序列可以看成是一個全新的序列
T1=【x2,x3,x4,x5,........xn?1,xn】T1=【x2,x3,x4,x5,........xn?1,xn】
序列T1T1可以認為是與之前的序列毫無關聯了。同樣的，我們可以對這個T1T1進行與TT相同的操作，直到TT中只一個元素為止。這樣我們就獲得了所有的可能性。所以很顯然，這是一個遞歸算法。
第一位的所有情況：無非是將x1x1與后面的所有數x2,x3,.......xnx2,x3,.......xn依次都交換一次
回溯算法的思路。?
?算法思路：全排列可以看做固定前i位，對第i+1位之后的再進行全排列，比如固定第一位，后面跟著n-1位的全排列。那么解決n-1位元素的全排列就能解決n位元素的全排列了，這樣的設計很容易就能用遞歸實現。
?代碼如下：
class Solution {List<List<Integer>> list=new ArrayList(); public List<List<Integer>> permute(int[] nums) {if(nums.length==0)return list;backTrace(0,nums.length,nums);return list;}public void backTrace(int i,int len,int [] nums){if(i==len-1){ //回溯的返回條件List<Integer> res=new ArrayList();for(int j=0;j<len;j++){ //回溯到了最后一個數字，我們便可以輸出數組 res.add(nums[j]);}list.add(res);return ;}for(int j=i;j<len;j++){swap(nums,i,j); //交換元素，全排列的思想backTrace(i+1,len,nums); //繼續回溯，改變i的值，使其向下探索swap(nums,i,j); //探索找到一個排列后，需要向上回溯，因此要恢復原序列的排列 }}public void swap(int[] nums,int i,int j){int temp=nums[i];nums[i]=nums[j];nums[j]=temp;} }
?
存在相同元素的情況
上面的程序乍一看沒有任何問題了。可是，如果我們對序列進行一下修改 array = {1, 2, 2}.我們看看運行的結果會怎么樣。
[1, 2, 2]
[1, 2, 2] [2, 1, 2] [2, 2, 1] [2, 2, 1] [2, 1, 2]這里出現了好多的重復。重復的原因當然是因為我們列舉了所有位置上的可能性，而沒有太多地關注其真實的數值。?
現在，我們這樣來思考一下，如果有一個序列T = {a1, a2, a3, …, ai, … , aj, … , an}。其中，a[i] = a[j]。那么是不是就可以說，在a[i]上，只要進行一次交換就可以了，a[j]可以直接忽略不計了。好了，基于這樣一個思路，我們對程序進行一些改進。我們每一次交換遞歸之前對元素進行檢查，如果這個元素在后面還存在數值相同的元素，那么我們就可以跳過進行下一次循環遞歸（當然你也可以反著來檢查某個元素之前是不是相同的元素）。?
基于這個思路，不難寫出改進的代碼。如下：
class Solution {List<List<Integer>> res=new ArrayList();public List<List<Integer>> permute(int[] nums) {dfs(nums,0);return res;}public boolean isSame(int[] nums,int start,int end){for(int i=start;i<end;i++){if(nums[i]==nums[end])return false;}return true;}public void dfs(int[] nums,int len){if(len==nums.length-1){List<Integer> list=new ArrayList();for(int i=0;i<nums.length;i++){list.add(nums[i]);}res.add(list);}for(int i=len;i<nums.length;i++){if(!isSame(nums,len,i))continue;swap(nums,i,len);dfs(nums,len+1);swap(nums,len,i);}}public void swap(int[] nums,int i,int j){int temp=nums[i];nums[i]=nums[j];nums[j]=temp;} }
回溯算法代碼？?
