47.全排列II

主要需要解決全排列不重復的問題，設定一個規則，保證在填第i個數的時候重復數字只會被填入一次即可，而在本題中，我們選擇對原數組排序，保證相同的數字都相鄰，然后每次填入的數一定是這個數所在重復數集合中「從左往右第一個未被填過的數字」

class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> tmp = new ArrayList<Integer>();int n = nums.length;boolean[] visites = new boolean[n];Arrays.sort(nums);backtrack(res,tmp,visites,nums);return res;}public void backtrack(List<List<Integer>> res,List<Integer> tmp,boolean[] visites,int[] nums){if(tmp.size() == nums.length){res.add(new ArrayList(tmp));return;}for(int i = 0; i < nums.length; i++){ //由于會有重復,保證在填第i個數的時候重復數組只會被填入一次即可//選擇對原數字排序，保證相同的數字都相鄰，然后每次填入的數一定是這個數所在重復數集合中從左往后第一個未被填過的數字//!visites[i-1]限制兩個相鄰的重復數字的訪問順序//比如[1,1,2]保證左邊的1永遠比右邊的1先使用/* vis[i]：當前數字是否出現過* 如果當前數字與前一個數字相同（nums[i] == nums[i - 1]），* 并且前一個數字還沒有出現的話（vis[i - 1] == false），* 那么就不能選擇當前數字（continue），* 如果前面的數字已經出現過（vis[i] == true），則可以* 選擇當前數字*/if(visites[i] || ( i>0 && nums[i] == nums[i -1] && !visites[i-1])){continue;}tmp.add(nums[i]);visites[i] = true;backtrack(res,tmp,visites,nums);tmp.remove(tmp.size()-1);visites[i]=false;}}
}