Subset

/***

9.4

return all subset of set.

***/

#include <iostream>

#include <vector>

using namespace std;

// Recursive, complexity is O(2^n)

void allsubset(int *a, int index, vector<vector<int>> *subsets) {

       if(index < 0) return;

       int sz = subsets->size();

       for(int i = 0; i<sz; i++) {

              vector<int> v;

              v = (*subsets)[i];

              v.push_back(a[index]);

              subsets->push_back(v);

       }

       allsubset(a, index-1, subsets);

}

void main() {

       int a[] = {1, 3, 5, 7};

       int sz = sizeof(a) / sizeof(int);

       vector<vector<int>> subsets;

       vector<int> v;

       subsets.push_back(v);

       allsubset(a, sz-1, &subsets);

       for (int i = 0; i<subsets.size(); i++)

       {

              for(int j=0; j<subsets[i].size(); j++)

                     cout<<"("<<subsets[i][j]<<", ";

              cout<<")"<<endl;

       }

}