Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets. For example,

If S = [1,2,2], a solution is:

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

The key is in the recursion, after processing the current element, if next element is duplicate skip it.

each element will at most add one more duplicate to the result.

public List<List<Integer>> subsetsWithDup(int[] num) {
        if (num==null) {
            return null;
        }
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        //All [] is a subset
        results.add(new ArrayList<Integer>());

        Arrays.sort(num);

        subsets(new ArrayList<Integer>(), results, 0, num);
        return results;        
    }

    public void subsets(List<Integer> result, List<List<Integer>> results, int level, int[] num) {
            for (int i=level; i<num.length; i++) {
                result.add(num[i]);                
                results.add(new ArrayList<Integer>(result));
                subsets(result, results, i+1, num);
                result.remove(result.size()-1);        
                while(i<num.length-1 && num[i]==num[i+1]) {
                    i++;
                }
            }
    }