Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Input: [1,1,2]Output:[  [1,1,2],  [1,2,1],  [2,1,1]]

难度：medium

题目：给定一组可能包含重复数的集合，返回所有可能的排列。

思路：先对数组进行排序，为去重做准备。然后借助递归遍历所有数。重点在于，当每次选定一个数做完交换之后，恢复时要对两个交换数及之间的所有数做排序。继续为接下来的去重做准备。

class Solution {    public List
    
     
      > permuteUnique(int[] nums) {        Arrays.sort(nums);        List
      
       
        > result = new ArrayList<>();        permuteUnique(nums, 0, new Stack
        
         (), result);                return result;    }        private void permuteUnique(int[] nums, int idx, Stack
         
           stack, List
          
           
            > result) { if (idx == nums.length) { result.add(new ArrayList<>(stack)); return; } for (int i = idx; i < nums.length; i++) { if (idx == i || nums[i] != nums[i - 1]) { stack.push(nums[i]); swap(nums, idx, i); permuteUnique(nums, idx + 1, stack, result); swap(nums, i, idx); Arrays.sort(nums, idx, i + 1); stack.pop(); } } } private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }}