本文共 1393 字，大约阅读时间需要 4 分钟。

1. 题目信息

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:输入: [1,2,2]输出:[  [2],  [1],  [1,2,2],  [2,2],  [1,2],  []]

来源：力扣（LeetCode）

2. 解题

类似题目

2.1 循环

参考别人的，比较难想出来。

class Solution {
   public:    vector
   
    
     > subsetsWithDup(vector
     
      & nums) {
           vector
      
        sub;        vector
       
        
         > ans; ans.push_back({ }); sort(nums.begin(), nums.end()); int i, j, left = 0, right; for(i = 0; i < nums.size(); ++i) { if(i != 0 && (nums[i-1] != nums[i])) left = 0; right = ans.size(); for(j = left; j < right; ++j) { sub = ans[j]; sub.push_back(nums[i]); ans.push_back(sub); } left = ans.size()-(right-left); } return ans; }};
        
       
      
     
    
   

2.2 回溯

class Solution {
   public:    vector
   
    
     > subsetsWithDup(vector
     
      & nums) {
           sort(nums.begin(), nums.end());        vector
      
        sub;        vector
       
        
         > ans; ans.push_back({ }); bt(nums,sub,ans,0); return ans; } void bt(vector
         
          & nums,vector
          
            sub, vector
           
            
             > &ans, int i) { for(int idx = i; idx < nums.size(); ++idx) { if(idx > i && nums[idx] == nums[idx-1]) continue; sub.push_back(nums[idx]); ans.push_back(sub); bt(nums,sub,ans,idx+1); sub.pop_back(); } }};
            
           
          
         
        
       
      
     
    
   

转载地址：https://michael.blog.csdn.net/article/details/100167394 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！