Given a collection of numbers that might contain duplicates, return all possible unique permutations.
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
permu(nums,res,new boolean[nums.length],new ArrayList<Integer>(),0);
return res;
}
public void permu(int[] nums,List<List<Integer>> res,boolean[] visited,ArrayList<Integer> cur,int index){
if(index == nums.length){
res.add(new ArrayList<Integer>(cur));
return;
}
for(int i = 0,len = nums.length;i<len;i++){
//避免逆序操作。
if(visited[i] || (i!=0&&nums[i-1] == nums[i] && !visited[i-1])){
continue;
}
visited[i] = true;
cur.add(nums[i]);
permu(nums,res,visited,cur,index+1);
visited[i] = false;
cur.remove(cur.size()-1);
}
}
}
