46 Permutations

　輸入一個(gè)不重復(fù)的數(shù)組 ，寫出這個(gè)數(shù)組的排列，不能重復(fù)。
　例如 輸入nums=[1,2,3]，輸出
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

　思路：可以看到 第0位（從左開(kāi)始數(shù)）有nums.length個(gè)數(shù)字可以選擇:1,2,3，在第0位確定以后，第1位有nums.length-1個(gè)數(shù)字可以選擇，例如p[0] = 1,p[1]只可能為2 或者3。所以重要的是記錄哪些下標(biāo)的元素已經(jīng)被選擇過(guò)。

public class Solution {private boolean[] p;//記錄選中過(guò)的下標(biāo)private List<List<Integer>> list;public List<List<Integer>> permute(int[] nums) {int[] newarray=new int[nums.length];//存放選中的數(shù)字p = new boolean[nums.length];list = new ArrayList<List<Integer>>();robot(0,newarray,nums);return list;}public void robot(int idx,int[] newarray,int[] nums){if(idx>=nums.length){List<Integer> l = new ArrayList<Integer>();for(int i=0;i<newarray.length;i++){l.add(newarray[i]);}list.add(l);return;}for(int i=0;i<nums.length;i++){if(p[i]==false){newarray[idx]=nums[i];p[i]=true;robot(idx+1,newarray,nums);p[i]=false;}}} }

47 Permutations II

　輸入一個(gè)重復(fù)的數(shù)組 ，寫出這個(gè)數(shù)組的排列，不能重復(fù)。
　例如輸入 [1,1,2] 輸出
[
[1,1,2],
[1,2,1],
[2,1,1]
]
　思路：這與46的區(qū)別是輸入的數(shù)組中有重復(fù)的數(shù)字。如果按照46的思路做，會(huì)出現(xiàn)重復(fù)的結(jié)果。我們先按照46的來(lái)做一下吧。用”數(shù)字(下標(biāo))”這種方式表示數(shù)組元素：1(0) 1(1) 2(2)。這樣才能把相同的數(shù)字區(qū)分開(kāi)來(lái)。為了方便，我們先將輸入的數(shù)組排序。按照46的思路得到以下組合：
1(0) 1(1) 2(2)
1(0) 2(2) 1(1)
1(1) 1(0) 2(2)
1(1) 2(2) 1(0)
2(2) 1(0) 1(1)
2(2) 1(1) 1(0)
　重點(diǎn)標(biāo)記的是重復(fù)的元素。分析一下。第0位可以選擇的元素有 nums[0], nums[1], nums[2]，但是當(dāng)已經(jīng)選擇nums[0]之后，再遇到nums[1]=nums[0]的時(shí)候，nums[1]是不能選擇的，否則就重復(fù)了。所以第0位可以選擇的元素有 nums[0], nums[2]。每一位都是，判斷nums[idx]能不能選擇標(biāo)準(zhǔn)是nums[idx-1]=nums[idx]是否為true。
這個(gè)判斷怎么加呢？下面記錄一下我自己犯過(guò)的錯(cuò)。

處理情況1

for(int i=0;i<nums.length;i++){if(p[i]==false){newarray[idx]=nums[i];p[i]=true;robot(idx+1,newarray,nums);p[i]=false;for (int j = i + 1; j < nums.length; j++){if (nums[j] != nums[j - 1]) {i = j - 1;break;}}}}

　每到一個(gè)位置，先選擇一個(gè)元素，再處理下一個(gè)元素和前面的元素是否相同。這里判斷的時(shí)候沒(méi)有考慮前面的元素是否會(huì)選中，可能會(huì)有多余的操作。更重要的是沒(méi)有處理如果重復(fù)元素是最后一個(gè)元素怎么處理。失敗用例：[1,1]。
　

for(int i=0;i<nums.length;i++){if(p[i]==false){newarray[idx]=nums[i];p[i]=true;robot(idx+1,newarray,nums);p[i]=false;int j = i + 1;for (; j < nums.length; j++){if (nums[j] != nums[j - 1]) {i = j - 1;break;}}if(j==nums.length){break;}}}

　改成這樣就對(duì)了。但是這樣代碼不夠優(yōu)雅。

處理情況2

for(int i=0;i<nums.length;i++){if(p[i]==false && (i==0 || (nums[i]!=newarray[idx]))){newarray[idx]=nums[i];p[i]=true;robot(idx+1,newarray,nums);p[i]=false;}}

　因?yàn)閚ewarray[idx]記錄了上一次選擇的值，所以想到只要判斷這次的候選值nums[i]和newarray[idx]不同就好了。這次的錯(cuò)誤是因?yàn)閕==0的判斷是有誤的。因?yàn)椴灰欢看味际莕ums[0]是第一個(gè)被選中的。例如當(dāng)?shù)?位選擇nums[0]，在選第2位的時(shí)候第一個(gè)被選中的一定是nums[1] ，所以這里應(yīng)該用一個(gè)boolean變量表示本次是不是對(duì)idx已經(jīng)選過(guò)一個(gè)值了。
　

boolean selected = false;for(int i=0;i<nums.length;i++){if(p[i]==false && (!selected || (nums[i]!=newarray[idx]))){selected = true;newarray[idx]=nums[i];p[i]=true;robot(idx+1,newarray,nums);p[i]=false;}}

處理情況3

　接著我還用了一種方式處理。使用了一個(gè)單獨(dú)的變量記錄在選擇idx的候選值時(shí)候，上一個(gè)選擇的值。

int preNum = -1;boolean selected = false;for(int i=0;i<nums.length;i++){if(p[i]==false && (selected==false || (nums[i]!=preNum))){selected = true;preNum = nums[i];newarray[idx]=nums[i];p[i]=true;robot(idx+1,newarray,nums);p[i]=false;}}

　總結(jié)：大概可以在編程的時(shí)候行不通。一定是一定可以才可以。在backtracing中最重要的是理解每一步的狀態(tài)。

總結(jié)

以上是生活随笔為你收集整理的leetcode之回溯backtracing专题2的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。