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

Solution: the same idea as Subset I, the only difference is that you may need to take care of duplicates. Here I give both DFS  and the iteration solutions.

   /*******************************SOLUTION 1***********************************/ 

class Solution {
public:
    void subsetsHelper(vector<vector<int> > &ret, vector<int> s, int cur, vector<int> r){
        if(cur==s.size()){
            ret.push_back(r);
            return;
        }
        //not add s[cur]
        subsetsHelper(ret, s, cur+1, r);
        //add s[cur]
        int c = 0;
        for(int i=0; i<r.size(); i++)
            if(r[i]==s[cur])
                c++;
        int d = 0;
        for(int i=0; i<cur; i++)
            if(s[i]==s[cur])
                d++;
        if(c==d){
            r.push_back(s[cur]);
            subsetsHelper(ret, s, cur+1, r);
        }
    }
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > ret;
        if(S.empty())  return ret;
        sort(S.begin(), S.end());
        vector<int> r;
        subsetsHelper(ret, S, 0, r);
        return ret;
    }
}; 

   /*******************************SOLUTION 1***********************************/

class Solution {
public:
    bool add(vector<int> s, vector<int> r, int cur){
        int c = 0;
        for(int i=0; i<r.size(); i++)
            if(r[i]==s[cur])
                c++;
        int d = 0;
        for(int i=0; i<cur; i++)
            if(s[i]==s[cur])
                d++;
        if(c==d)
            return true;
        return false;
    }
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > ret;
        if(S.empty())  return ret;
        sort(S.begin(), S.end());
        vector<int> r;
        ret.push_back(r);
        for(int i=0; i<S.size(); i++){
            int num = ret.size();
            for(int j=0; j<num; j++){
                if(add(S, ret[j], i)){
                    r = ret[j];
                    r.push_back(S[i]);
                    ret.push_back(r);
                }
            }
        }
        return ret;
    }
};