T47. Permutations II【Medium】
題目
給出一個可以包含重復(fù)數(shù)字的數(shù)字集隅居，返回所有可能的不重復(fù)排列組合。
例如瞎惫，
[1,1,2] 有如下的排列組合：
[
[1,1,2],
[1,2,1],
[2,1,1]
]
思路
這題的大體想法和上題一樣溜腐，不過除了遞歸译株，這題還要對重復(fù)怎么判斷進行處理，以及防止重復(fù)排列組合的出現(xiàn)挺益。
① 遞歸
思路和上一題差不多歉糜，如下：
排列組合（1 2 3）
= 1 + 排列組合（2 3）∪ 2 + 排列組合（1 3）∪ 3 + 排列組合（1 2）
排列組合（2 3）
= 2 + 排列組合（3）∪ 3 + 排列組合（2）
= 23 ∪ 32
可以看出在數(shù)字只有一個的時候到了遞歸的終點
② 重復(fù)判別
上一題是直接看這個數(shù)有沒有用過，那是基于這個數(shù)只出現(xiàn)一遍望众，而在這題可以出現(xiàn)重復(fù)的數(shù)字這個方法就不可用了匪补。這個 Solution 用了什么解決方法呢，看下面：
boolean[] used = new boolean[nums.length];
建立了一個 boolean 的數(shù)組和 nums 中的數(shù)一一對應(yīng),然后用
used[i]=true;
used[i]=false;
的設(shè)置來表示這個數(shù)是否用過
然后用在循環(huán)中加入下面的語句來跳過用過的數(shù)字
if(used[i]) continue;
③ 排除重復(fù)排列組合
造成重復(fù)排列組合的原因可以動手寫一下看看~
避免這種重復(fù)的方法在于后面重復(fù)的數(shù)不能排在前面重復(fù)的數(shù)前面（可能有點繞烂翰，最好動手寫寫看）夯缺。
代碼則是很簡單，像下面這樣：
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
因為已經(jīng)排好序了刽酱，所以若 nums[i-1]==nums[i] 和 !used[i-1] 則代表它之前的重復(fù)的數(shù)沒有被用到喳逛，這時，跳過這次循環(huán)棵里，因為它也不應(yīng)該被用润文。
另外，不能寫成
if(i>0 &nums[i-1]==nums[i] & !used[i-1]) continue;
可以想一下原因~我在補充里說殿怜！
代碼
代碼取自 Top Solution典蝌，稍作注釋
public List<List<Integer>> permuteUnique(int[] nums) {
//建立要返回的數(shù)據(jù)形式
List<List<Integer>> res = new ArrayList<List<Integer>>();
//若為空,直接返回
if(nums==null || nums.length==0) return res;
//建立 used 數(shù)組來判斷這個數(shù)字是否用過
boolean[] used = new boolean[nums.length];
List<Integer> list = new ArrayList<Integer>();
//排序
Arrays.sort(nums);
dfs(nums, used, list, res);
return res;
}
public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
//若所有元素都用到了(達到長度)則加到 ArrayList 里面
if(list.size()==nums.length){
res.add(new ArrayList<Integer>(list));
return;
}
for(int i=0;i<nums.length;i++){
//若用到過這個數(shù)字了,則跳過本次循環(huán)
if(used[i]) continue;
//用這句來避免重復(fù)
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
//設(shè)置為true代表已經(jīng)用過
used[i]=true;
//下面四行是遞歸,看和上一題差不多,看"思路"里
list.add(nums[i]);
dfs(nums,used,list,res);
used[i]=false;
list.remove(list.size()-1);
}
}
補充
關(guān)于
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
為什么要用 "&&" 而不用 "&"?
我們可以嘗試先把 "&&" 改成 "&"，然后發(fā)現(xiàn)會報錯头谜！
為什么呢骏掀？我的編譯器不愛我了嗎？
這要先講一下兩者的區(qū)別：
&&和&都是表示與柱告，區(qū)別是&&只要第一個條件不滿足截驮，后面條件就不再判斷。而&要對所有的條件都進行判斷际度。
因為當(dāng)用了 && 時葵袭，執(zhí)行 i>0 為 false 時就不往下執(zhí)行了，而用 & 時會把這三個都執(zhí)行一遍乖菱，在執(zhí)行
nums[i-1]==nums[i]
的時候 nums[i-1] 是 nums[-1],會報 ArrayIndexOutOfBoundsException 的錯誤坡锡。
