90. Subsets II Leetcode Java

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:

This problem is the advanced and more general problem of 78. Subsets

For this problem, duplicates is allowed in the array, so how to avoid duplicate subsets is the focus point.

If A[i]!=A[i-1], which is the same case as problem 78: Add the new element for all subsets in the result list and add the newly generated subsets into result list.

If A[i]==A[i-1], eg.[1,2,2] i=2, result list{[],[1],[2],[1,2]}, obviously, if we follow the original solution, it will generate two duplicate subsets [2],[1,2], so we have to add the A[i]=2 only to these two subsets[2],[1,2] and only generates[2,2],[1,2,2]. Clearly, the duplicated element can't add to the res[n-2] twice, so the starting point will be the size of res[n-2] rather than 0. Thus we can avoid the duplicates subsets.

 public List<List<Integer>> subsetsWithDup(int[] num) {  
     if(num==null) return null;  
     List<List<Integer>> res=new ArrayList<List<Integer>>();  
     List<Integer> subSets=new ArrayList<Integer>();  
     res.add(subSets);  
     if(num.length==0) return res;  
     Arrays.sort(num);  
     int start=0;  
     int l=0;  
     for(int i=0;i<num.length;i++){  
       start=l;  
       if(i!=0 && num[i]!=num[i-1]) start=0;  
       l=res.size();  
       for(int j=start;j<l;j++){  
         List<Integer> temp=new ArrayList<Integer>(res.get(j));  
         temp.add(num[i]);  
         res.add(temp);  
       }  
     }  
     return res;  
   }