Given a list of numbers that may has duplicate numbers, return all possible subsets. Each element in a subset must be in non-descending order. The ordering between two subsets is free. The solution set must not contain duplicate subsets.

Example

For numbers [1, 2, 2] the unique permutations are:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Recursive solution:

class Solution {
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> S) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int stop = (int)Math.pow(2, S.size());
        for (int bitmap = 0; bitmap < stop; bitmap++) {
            ArrayList<Integer> set = new ArrayList<>();
            int mask = 1, j = 0;
            while (mask < stop) {
                if ((bitmap & mask) != 0)
                    set.add(S.get(j));
                mask <<= 1;
                j++;
            }
            Collections.sort(set);
            if (!res.contains(set))
                res.add(set);
        }
        return res;
    }
}