Subsets II

subsetsWithDup.java

/*
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],
  []
]

Algorithm:
1. Normal subset algorithm with additional logic:
    a. Sorted the original array of integer num
    b. Check if the num[i] == num[i-1], then check if i-1 havent check,
        then it is ok to continue, or stop

*/
public class Solution {
    HashSet<Integer> seen;
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if(num.length == 0) return ret;
        seen = new HashSet<Integer>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        Arrays.sort(num);
        ret.add(list);
        subsetHelper(num, 0, ret, list);
        return ret;
    }
    
    public void subsetHelper(int[] num, int start, ArrayList<ArrayList<Integer>> ret, ArrayList<Integer> list) {
        for(int i = start; i < num.length; i++) {
            if(i > 0 && num[i] == num[i-1] && !seen.contains(i-1)) continue;
            list.add(num[i]);
            seen.add(i);
            ret.add(new ArrayList<Integer>(list));
            subsetHelper(num, i+1, ret, list);
            list.remove(list.size() - 1);
            seen.remove(i);
        }
        
        return;
    }
}