SubsetII

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] S) {
        Arrays.sort(S);
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        
        boolean []selected = new boolean[S.length];

        subset(S, 0, selected, ans);
        return ans;
    }
    
    private void subset(int[] S, int i, boolean []selected, ArrayList<ArrayList<Integer>> ans) {
        if (i == S.length) {
            ArrayList<Integer> t = new ArrayList<Integer>();
            for (int j = 0; j < selected.length; j++) {
                if (selected[j])
                  t.add(S[j]);
            }
            ans.add(t);
        } else {
            int j = i + 1;
            while (j < selected.length && S[j] == S[i]) {
                j++;
            }
            selected[i] = true;
            subset(S, i + 1, selected, ans);
            
            selected[i] = false;
            subset(S, j, selected, ans);
        }
    }
}