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

permuteUnique.java

/*
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 boolean[] used;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (num.length == 0) return results;
        used = new boolean[num.length];
        Arrays.sort(num);
        permute(num, list, results);
        
        return results;
    }
    
    public void permute(int[] num, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> results) {
        if (num.length == list.size()) {
            results.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i = 0; i < num.length; i++) {
            if ((used[i]) || (i != 0 && num[i] == num[i-1] && used[i-1])) continue;
            // try
            list.add(num[i]);
            used[i] = true;

            // next
            permute(num, list, results);
            
            // rework
            list.remove(list.size() - 1);
            used[i] = false;
        }
    }
}