Subsets II

The tricky part of this question is the duplicate numbers in array.

Algorithm for it should be very simple: start from empty subset, set previous result contains this empty subset, add each element in array to every single element in previous result, check whether the newly produced element has been contained, if not, add it to current result. One thing we need to be aware is that the previous result I mention here is result from last loop. And similarly, current result is just result we get in current loop.

Repeat above process until we add a result whose size is equal to length of array. This result should contain all the elements in array, which means no more elements can be added. Thus it is the last subset.

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] num) {
        if(num.length == 0) return null;
       
        Arrays.sort(num);
        // Note: List<> can not be "new", i.e. it can not be instantiated
        LinkedList<List<Integer>> res= new LinkedList<List<Integer>>();
        LinkedList<List<Integer>> preRes= new LinkedList<List<Integer>>();
        LinkedList<List<Integer>> crntRes= new LinkedList<List<Integer>>();
       
        HashMap<Integer,Integer> numMap = new HashMap<Integer,Integer>();
        initMap(numMap,num);
        LinkedList<Integer> subset = new LinkedList<Integer>();
        res.add(subset);
        preRes.add(subset);
        while(!preRes.isEmpty()){
        for(int t = 0; t < preRes.size(); t++){
          
            for(int i = 0; i < num.length; i++){
                List<Integer> tmpSubset = copy(preRes.get(t));
                int aprTimes = findTimes(tmpSubset,num[i]);
                if(aprTimes < numMap.get(num[i])){
                    tmpSubset.add(num[i]);
                    Collections.sort(tmpSubset,new IntCompare());
                    if(!crntRes.contains(tmpSubset)){
                        crntRes.add(tmpSubset);
                        if(tmpSubset.size() == num.length){
                            res.addAll(crntRes);
                            return res;
                        }
                    }
                }
            }
           
        }
        res.addAll(crntRes);
        preRes = crntRes;
        crntRes = new LinkedList<List<Integer>>();
        }
        return res;
    }
    public int findTimes(List<Integer> subset, int num){
        if(subset.isEmpty()) return 0;
        int times = 0;
        for(int i = 0; i < subset.size();i++){
            if(subset.get(i) == num) times ++;
        }
        return times;
    }
    public void initMap(HashMap<Integer,Integer> numMap,int[] num){
        for(int i = 0; i < num.length; i++){
            if (numMap.containsKey(num[i])){
                int times = numMap.get(num[i]);
                times++;
                numMap.put(num[i], times);
            }
            else numMap.put(num[i], 1);
        }
    }
   
    class IntCompare implements Comparator<Integer>{
        public int compare(Integer i1, Integer i2){
            return i1.compareTo(i2);
        }
    }
   
    public List<Integer> copy( List<Integer> l1){
        LinkedList<Integer> l2 = new LinkedList<Integer>();
        for(int i = 0; i < l1.size();i++) l2.add(l1.get(i));
        return l2;
    }
}