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

Almost the same as Permutations, but since there will be duplicate element in the array, before entering the recursion, we need to check whether the previous element is used or not if used, whether it is the same as current element.

public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        if (num==null||num.length==0) {
            return results;
        }

        Arrays.sort(num);
        permuteUnique(results, new ArrayList<Integer>(), num, new boolean[num.length]);

        return results;
    }

    public void permuteUnique(List<List<Integer>> results, List<Integer> result, int[] num, boolean[] used) {
        if (result.size()==num.length) {
            results.add(new ArrayList<Integer>(result));
            return;
        }

        for (int i=0; i<num.length; i++) {
            if (i>0&&used[i-1]&&num[i]==num[i-1]) continue;
            if(!used[i]) {
                result.add(num[i]);
                used[i]=true;
                permuteUnique(results, result, num, used);
                used[i]=false;
                result.remove(result.size()-1);
            }
        }
    }