Permutations with duplicates

1. Non-recursive solution

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    if(nums.length==0) return res;
    res.add(new ArrayList<Integer>());
    for(int n:nums){
        List<List<Integer>> next=new ArrayList<List<Integer>>();
        for(List<Integer> list:res){
            for(int i=0;i<=list.size();i++){
                List<Integer> nextList=new ArrayList<Integer>(list);
                if(i==list.size()) {nextList.add(n); next.add(nextList); break;}
                nextList.add(i,n);
                next.add(nextList);
                if(list.get(i)==n) break; // this line deal with the duplicates
            }
        }
        res=next;
    }
    return res;
}

1. Recursive solution

public class Solution {
    public List<List<Integer>> permuteUnique(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);
        permute(list, 0, res);
        return res;
    }
    private void permute(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)) // this line deal with the duplicates
                continue;
            nums.add(start, nums.get(i)); // put ith element in the fornt
            nums.remove(i + 1); // remove the moved element, now it is in (i+1)th position
            permute(nums, start + 1, res); // permute the rest
            nums.add(i + 1, nums.get(start)); // put the moved element back
            nums.remove(start); // delete the residual 
        }
    }
}