Share my recursive and iterative solutions


  • 1
    S
    // iterative method to get each element
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > ans(1, vector<int>());
        sort(S.begin(), S.end());
        
        vector<int> tmp;
        for (int i = 0; i < S.size(); ++i) {
            int len = ans.size();
            for (int j = 0; j < len; ++j) {
                tmp = ans[j];
                tmp.push_back(S[i]);
                ans.push_back(tmp);
            }
        }
        
        return ans;
    }
    
    // recursive backtracing
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > ans;
        if (S.size() <= 0) return ans;
        
        sort(S.begin(), S.end());
        if (S.size() == 1) {
            ans.push_back(vector<int>());
            ans.push_back(S);
            return ans;
        }
        
        vector<int> tmp;
        vector<int> a(S.begin()+1, S.end());
        ans = subsets(a);
        int n = ans.size();
        for (int i = 0; i < n; ++i) {
            tmp = ans[i];
            tmp.insert(tmp.begin(), *S.begin());
            ans.push_back(tmp);
        }
        
        return ans;
    }

  • 0

    Many thanks.
    Your recursive version is still taking use of the iteration idea following the first version.
    The complete recursive version will need to call subsets twice inside subsets which is really hard to track by human mind.
    Nice post anyway.


Log in to reply
 

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