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

Solution:
n->n+1 question, and use Hash Map to get rid of duplicates.

public class Solution {
    public ArrayList> subsetsWithDup(int[] num) {
        ArrayList> result = new ArrayList>();
        HashMap, Boolean> hash = new HashMap, Boolean>();
        result.add(new ArrayList());
        hash.put(new ArrayList(), true);
        if(num.length == 0) return result;
        Arrays.sort(num);
        for(int i = 0; i < num.length; i++){
            ArrayList> tempRes = new ArrayList>();
            ArrayList tempList = new ArrayList();
            for(ArrayList iter : result){
                ArrayList cur = new ArrayList(iter);
                cur.add(num[i]);
                tempRes.add(cur);
            }
            for(int j = 0; j < tempRes.size(); j++){
                tempList = tempRes.get(j);
                if(!hash.containsKey(tempList)){
                    result.add(tempList);
                    hash.put(tempList, true);
                }
            }
        }
        return result;
    }
}