Leetcode--Subsets II

Problem Description:

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],
    []
  ]

  分析：要求打印出所有不重复的组合，可以利用一个flag数组记录当前元素是否已被使用，然后判断之前该元素是否已被重复使用，所有组合为包含和不包含当前元素的总和，具体代码如下：

  class Solution {
  public:
  
      void dfs(vector
      
        &s, int beg, int len, vector
       
         &mid, vector
        
          > &res,vector
         
           &flag) { if(len==0) { res.push_back(mid); return; } if(beg==s.size()) return; if(beg==0||s[beg]!=s[beg-1]||(s[beg]==s[beg-1]&&flag[beg-1]==1))//选中当前元素 { mid.push_back(s[beg]); flag[beg]=1; dfs(s,beg+1,len-1,mid,res,flag); flag[beg]=0; mid.pop_back(); dfs(s,beg+1,len,mid,res,flag); } else //不选中当前元素 { dfs(s,beg+1,len,mid,res,flag); } } vector
          
            > subsetsWithDup(vector
           
             &S) { vector
            
              > res; int len=S.size(); if(len==0) return res; vector
             
               mid; vector
              
                flag(len,0); sort(S.begin(),S.end()); for(int i=0;i<=len;++i)//长度为0到len的组合 dfs(S,0,i,mid,res,flag); } };