原题链接在这里：

题目：

Given a collection of integers that might contain duplicates, nums, 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 nums = [1,2,2], a solution is:

[  [2],  [1],  [1,2,2],  [2,2],  [1,2],  []]

题解：

是的进阶版本。这里有duplicates, e.g. [1,2,2]但是res中不能包含两个[2].

还是backtracking, 注意去重.

Time Complexity: exponential. Space: O(nums.length). stack space.

AC Java:

1 class Solution { 2     public List
     
      
       > subsetsWithDup(int[] nums) { 3         List
       
        
         > res = new ArrayList
         
          
           >(); 4 Arrays.sort(nums); 5 dfs(nums, 0, new ArrayList
           
            (), res); 6 return res; 7 } 8 9 private void dfs(int [] nums, int start, List
            
              item, List
             
              
               > res){10 res.add(new ArrayList
               
                (item));11 for(int i = start; i
                
                 start && nums[i]==nums[i-1]){13 continue;14 }15 item.add(nums[i]);16 dfs(nums, i+1, item, res);17 item.remove(item.size()-1);18 }19 }20 }
                
               
              
             
            
           
          
         
        
       
      
     

也所以在elem加完新元素想要放回res之前，需要先判断res中是否含有这个elem, 若是没有可以加到res中，若是已经有了，就不可以加到res中.

Time Complexity: exponential. Space: O(res.size()).

AC Java:

1 public class Solution { 2     public List
     
      
       > subsetsWithDup(int[] nums) { 3         List
       
        
         > res = new ArrayList
         
          
           >(); 4 if(nums == null || nums.length == 0){ 5 return res; 6 } 7 Arrays.sort(nums); 8 res.add(new ArrayList
           
            ()); 9 for(int i = 0; i
            
              elem = new ArrayList
             
              (res.get(j));13 elem.add(nums[i]);14 if(!res.contains(elem)){15 res.add(elem);16 }17 }18 }19 return res;20 }21 }