[LeetCode] Subsets II

Problem:

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:O(n)

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(num == null || num.length == 0)
            return list;
        
        if(num.length == 1){
         list.add(new ArrayList<Integer>());
         ArrayList<Integer> s2 = new ArrayList<>();
         s2.add(num[0]);
         list.add(s2);
         return list;
        }
        
        int[] num1 = Arrays.copyOfRange(num, 0, num.length-1);
        ArrayList<ArrayList<Integer>> slist =  subsetsWithDup(num1);    
        HashMap<ArrayList<Integer>,Boolean> map = new HashMap<>();
   
        for(int i=0; i<slist.size();i++){
            ArrayList<Integer> t = new ArrayList<Integer>(slist.get(i));
            list.add(t);
            map.put(t,true);
        }
        
        for(int i=0; i<slist.size();i++ ){
            ArrayList<Integer> t= new  ArrayList<Integer>(slist.get(i));
            t.add(num[num.length-1]);
            if(map.get(t) == null){
                map.put(t,true);
                list.add(t);
            }
        }
         return list;
    }
}