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

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

*/

//from programcreek
public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        
        if (num == null)
            return null;
            
        Arrays.sort(num);
        
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<ArrayList<Integer>> prev = new ArrayList<ArrayList<Integer>>();
        
        for (int i = num.length - 1; i >= 0; i--) {
            
            //get the existed sets
            if (i == num.length - 1 || num[i] != num[i+1] || prev.size() == 0) {
                prev = new ArrayList<ArrayList<Integer>>();
                for (int j = 0; j < result.size(); j++) {
                    prev.add(new ArrayList<Integer>(result.get(j)));
                }
            }
            
            //add curretn num into sets
            for (ArrayList<Integer> a : prev) {
                a.add(0, num[i]);
            }
            
            //add each single num as a single set
            if (i == num.length - 1 || num[i] != num[i+1]) {
                ArrayList<Integer> temp = new ArrayList<Integer>();
                temp.add(num[i]);
                prev.add(temp);
            }
            
            //add all set created
            for (ArrayList<Integer> a : prev) {
                result.add(new ArrayList<Integer>(a));
            }
            
        }
        //add empty set
        result.add(new ArrayList<Integer>());
        
        return result;
    }
}