Subsets II--LeetCode

ゝ一纸荒年。 2022-08-07 11:44 136阅读 0赞

# 题目： #

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

思路：和上面一样的思路

vector<vector<int> >  v;  
        vector<vector<int> > subsetsWithDup(vector<int> &S) {  
            sort(S.begin(),S.end());  
              
            generate(vector<int>(), S, 0);  
            return v;  
        }  
          
        void generate(vector<int> res, vector<int> &S, int i)  
        {  
            if(i == S.size())  
            {  
                for(int i = 0; i < v.size(); i++)  
                {  
                    if(v[i] == res)  
                    {  
                        return;  
                    }  
                }  
                v.push_back(res);  
                return;  
            }  
            else  
            {  
                generate(res, S, i+1);  
                res.push_back(S[i]);  
                generate(res, S, i+1);  
            }  
        }

或者将上面的一个helpr函数替换

void helper_array(vector<int>& vec,int begin,int& k,vector<int>& com)  
    {  
        if(begin >= vec.size() || k <0)  
            return ;  
        com.push_back(vec[begin]);  
        k--;  
        if(k == 0)  
        {  
            int i;  
            for(i=0;i<com.size();i++)  
                cout<<com[i]<<" ";  
            cout<<endl;  
              
        }  
        helper_array(vec,begin+1,k,com);  
        com.pop_back();  
        k++;  
        int i;  
        for(i=begin+1;i<vec.size();)  
        {  
            if(vec[i] == vec[begin])  
                i++;  
            else  
                break;  
        }  
        helper_array(vec,i,k,com);  
          
    }