Get all subsets from a given set using recursion. O(2^n) complexity.

subsets.cpp

void getss(vector<int>& x, int index, vector<vector<int>>& all){
    if ( index > x.size() || index < 0 ) return;
    if (index == 0 ){
        vector<int> empty;
        all.push_back(empty);
        getss(x,index+1,all);
    }
    else{
        vector<vector<int>> copyall(all);
        for( auto i = copyall.begin(); i != copyall.end(); ++i){
            i->push_back(x[index-1]);
            all.push_back(*i);
        }        
        getss(x,index+1,all);
    }
    
}


int main() {
    int d[] = {1,2,3};
    vector<int> orig(begin(d), end(d));
    vector<vector<int>> subsets;
    getss(orig, 0, subsets);
    cout << subsets.size() << endl;
     for( auto i = subsets.begin(); i != subsets.end(); ++i){
         for( auto j = (*i).begin(); j != (*i).end(); ++j){
             cout << *j << " ";
         }
         cout << endl;
     }
    cout << "done " << endl;
    std::cin.get();
    return 0;
}

/*
What is the difference between the solution for n = Sand the solution for n = 2? Let's
look at this more deeply:
P(2) - {}, {aj, {a2}, {aaJ a2}
P(3) = {}, (aj, {aj, {a3}, {aa, a2}, {a^ a3}, {a2, a3},
{aj, a2, a3}
The difference between these solutions is that P(2) is missing all the subsets containing
ar
P(3) - P(2) = {aj, {3lJ a,}, {a2J a3}, {a,, a2, a3}
How can we use P(2) to create P( 3)? We can simply clone the subsets in P(2) and add
a3 to them:
P(2) 
= {} , {aj, {aj, {9lJ a2}
P(2) + a3 
= {a3}, {at, aj, {a2, a3}, {aaJ a2, a3}
When merged together, the lines above make P(3).





*/