public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] S) {
        // Sort first
        Arrays.sort(S);

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        // create a boolean array to track progress
        boolean[] b = new boolean[S.length];
        while (true) {
            // output a good subset
            result.add(getR(b, S));
            int i = 0;
            while (i < S.length) {
                if (b[i] == false) {
                    // if current position is false, just market it true and break;
                    b[i] = true;
                    break;
                } else {
                    // see if next position has same character
                    int k=i+1;
                    while(k<S.length&&S[k]==S[i]&&b[k]==true){
                        k++;
                    }
                    if(k==S.length){
                        // reach the end, break;
                        i=k;
                        break;
                    }
                    if(S[k]==S[i]){
                        // found a dup character that has false, just mark it true and break;
                        b[k]=true;
                        break;
                    }else{
                        // all same dup is true, mark everything false and go on
                        while(i<k){
                            b[i] = false;
                            i++;
                        }
                    }
                }
            }
            if (i == S.length)
                break;
        }
        return result;
    }
   
    public ArrayList<Integer> getR(boolean[]b,int[]S) {
        ArrayList<Integer> r=new ArrayList<Integer>();
        for(int i=0;i<b.length;i++){
            if(b[i])r.add(S[i]);
        }
        return r;
    }
}