Share My 14ms C++ Solution with Explanation


  • 0
    H

    We use a similar way to solve this problem as it's in the SubSet I(traverse the entire vector and either or not to put the current element in each of the result set we already get before, thus we have a result set of 2^n).
    Here, we think about two subsets x, x+a(where x might be empty). If the traversing element equals a, we can only extend x to {x, x+a} where x is not empty, x+a to {x+2a}; Notice that if x here is empty, so we would get {[], a}, {2a}, which would definitely cause a duplication cause {a} is already in the subsets when we first traverse the element a. If the traversing element doesn't equals a, it's ok to extend x to {x, x+b}, x+a to {x+a, x+a+b}. Thus, the solution is as clear as above:

    class Solution {
        public:
            vector<vector<int> > subsetsWithDup(vector<int> &S) {
                vector<vector<int> > res(1, vector<int>());
                if(S.empty()) {
                    return res;
                }   
                sort(S.begin(), S.end());
                res.push_back(vector<int>(1, S[0]));
                for(int i=1; i<S.size(); ++i) {
                    int size = res.size();
                    for(int j=0; j<size; ++j) {
                        int jsize = res[j].size();
                        if(S[i] == S[i-1] && (res[j].size() > 1 && res[j][jsize-1] == S[i])) {
                            res[j].push_back(S[i]);
                        }
                        else if(S[i] != S[i-1] || res[j].size() > 0){
                            vector<int> temp(res[j].begin(), res[j].end());
                            temp.push_back(S[i]);
                            res.push_back(temp);
                        }
                    }
                }                                                                                                                                   
                return res; 
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.