47. Permutations II

[huimeich]

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].

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new LinkedList<List<Integer>> ();
        List<Integer> soFar = new LinkedList<Integer>();
        Arrays.sort(nums);
        if (nums.length == 0) return res;
        soFar.add(nums[0]);
        res.add(new LinkedList<Integer>(soFar));
        for (int start = 1; start < nums.length; start++) {
            for (int r_size = res.size() - 1; r_size >= 0; r_size--){
                soFar = res.remove(0);
                for (int i = 0; i <= start; i++) {
                    if (i >= soFar.size()) {
                        soFar.add(nums[start]);
                        res.add(new LinkedList<>(soFar));
                        soFar.remove(soFar.size() - 1);
                        break;
                    } else {
                        soFar.add(i, nums[start]);
                        res.add(new LinkedList<>(soFar));
                        soFar.remove(i);
                        if (soFar.get(i) == nums[start]) break;
                    }
                }
            }
        }
        return res;
    }
}

[huimeich]

Recursive

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new LinkedList<List<Integer>> ();
        List<Integer> soFar = new LinkedList<Integer>();  
        Arrays.sort(nums);
        for (int i : nums)  soFar.add(i);
        res = permuteUniqueHelper(res, 0, soFar);
        return res;
    }

    private List<List<Integer>> permuteUniqueHelper(List<List<Integer>> res, int start, List<Integer> soFar) {
        if (start == soFar.size() - 1) {
            res.add(new LinkedList<Integer>(soFar));
            return res;
        }
        for (int i = start; i < soFar.size(); i++) {
            if (i != start && soFar.get(start) == soFar.get(i)) continue;
            Collections.swap(soFar,i,start);
            res = permuteUniqueHelper(res, start + 1, new LinkedList<Integer>(soFar));
        }
        return res;
    }
}