給定一個沒有重復數字的序列,返回其所有可能的全排列。
示例:
輸入: [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;} }
回溯算法代碼??