Subsets II--LeetCode

题目：

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);  
}