Very simple none recursive C++ solution with add 1 trick


  • 0
    E

    The core idea is that if you want to get the subsets of n numbers, for example 3, you should range the index from 000 to 111, this is actually to add 1 from 0 to 7. So you get the indexes, you can get the subsets!

    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > ret;
        if(S.empty())
            return ret;
        auto n = S.size();
        unsigned int index = 0;
        while(((1 << n) & index) == 0)
        {
            vector<int> temp;
            int i = 1;
            for(int j=0; j<n; ++j)
            {
                if((i & index) > 0)
                    temp.push_back(S[j]);
                i <<= 1;
            }
            sort(temp.begin(), temp.end());
            ret.push_back(temp);
            ++index;
        }
        return ret;
    }

Log in to reply
 

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