*Permutations II

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

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

好解法：和i中那个arraylist的对应！！！！！

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int num : nums) list.add(num);
        perm(list, 0, res);
        return res;
    }
    private void perm(LinkedList<Integer> nums, int start, List<List<Integer>> res){
        if (start == nums.size() - 1){
            res.add(new LinkedList<Integer>(nums));
            return;
        }
        for (int i = start; i < nums.size(); i++){
            if (i > start && nums.get(i) == nums.get(i - 1)) continue;
            nums.add(start, nums.get(i));
            nums.remove(i + 1);
            perm(nums, start + 1, res);
            nums.add(i + 1, nums.get(start));
            nums.remove(start);
        }
    }
}

无救了的解法，160ms，打败0.6%...

public class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    HashSet<List<Integer>> set = new HashSet<List<Integer>>(); 

    public List<List<Integer>> permuteUnique(int[] nums) 
    {
        int k = 0;
        int m = nums.length-1;
        perm(nums,k,m);
        for (List<Integer> subset : set) {
            res.add(new ArrayList<Integer> (subset));
        }
        
        return res;
    }
    
    public void perm(int[] nums, int k, int m)
    {
        if(k==m)
        {
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<=m;i++)
            {
                list.add(nums[i]);
            }
            set.add(list);
        }
        else
           for( int i=k; i<=m; i++)
           {
                 swap(nums,k,i);
                 perm(nums, k+1, m);
                 swap(nums,k,i);
           }
    }
    
    public int[] swap(int[] nums, int k, int i)
    {
        int temp = nums[k];
        nums[k] = nums[i];
        nums[i] = temp;
        return nums;
    }
}