How to write C++ version of Python powerset function -

i want write maximal clique algorithm use adjacency matrix. i'm following video explains how code , implement algorithm using python. i'm trying code powerset function @ 2 minutes video.

def powerset(elts):     if len(elts) == 0:         return [[]]     else:         smaller = powerset(elts[1:])         elt = [elts[0]]         withelt = []         s in smaller:             withelt.append(s + elt)         allofthem = smaller + withelt     return allofthem  print powerset([1, 2, 3, 4, 5]) 

i want rewrite in c++. i'm not sure if should using arrays or not. far have coded below don't know how return empty array inside empty array (when elts list of size 0).

i wrote isempty function array since cant use len(elts) in python. approach not best approach take open advice.

update:

array powerset(int elts[]) {      if (isempty(elts)==1)      {           return {{}};      }  } 

in int main have:

list<int> elts;  list<int>::iterator i;  (i=elts.begin(); != elts.end(); ++i)       cout << *i << " ";       cout << endl;  powerset(elts);     

i don't know here.

the code should use either array/list/vector call 'elts' (short elements). firstly, should add empty list [], rest of power set (all shown in video).

so example, in case elts = [1,2,3,4], code should return:

`[ [],[4],[3],[4,3],[2],[4,2],[3,2],[4,3,2],[1],[4,1],[3,1],[4,3,1],[2,1],[4,2,1],[‌​3,2,1],[4,3,2,1] ]  `   

i don't know how use array/list/vector above.

here's literal translation of python code

#include <vector> using std::vector; #include <iostream> using std::cout;  //def powerset(elts): vector<vector<int>> powerset(const vector<int>& elts) { //  if len(elts) == 0:     if (elts.empty()) { //      return [[]]         return vector<vector<int>>(             1, // vector contains 1 element is...             vector<int>()); // ...empty vector of ints     } //  else:     else { //      smaller = powerset(elts[1:])         vector<vector<int>> smaller = powerset(             vector<int>(elts.begin() +1, elts.end())); //      elt = [elts[0]]         int elt = elts[0]; // in python elt list (of int) //      withelt = []         vector<vector<int>> withelt; //      s in smaller:         (const vector<int>& s: smaller) { //          withelt.append(s + elt)             withelt.push_back(s);             withelt.back().push_back(elt);         } //      allofthem = smaller + withelt         vector<vector<int>> allofthem(smaller);         allofthem.insert(allofthem.end(), withelt.begin(), withelt.end()); //      return allofthem         return allofthem;     } } 

this uses vector<int> set of integers. , vector of this, i.e. vector<vector<int>> list of sets of integers. asked 1 thing

i don't know how return empty array inside empty array (when elts list of size 0).

the first return statement returns list 1 element, empty set, using vector constructor, first argument n number of elements in vector, , second argument element repeat n times. equivalent more long-winded alternative is

    vector<vector<int>> powersetofemptyset;     vector<int> emptyset;     powersetofemptyset.push_back(emptyset);     return powersetofemptyset; 

i've tried keep code simple , avoid many esoteric c++ features. can work through aid of reference. 1 c++ idiom have used appending 1 vector in allofthem.insert(allofthem.end(), withelt.begin(), withelt.end());.

also in c++, "closer metal" python, use 1 vector in place of 3 vectors smaller, withelt , allofthem. leads shorter , more optimal code below.

//def powerset(elts): vector<vector<int>> powerset(const vector<int>& elts) { //  if len(elts) == 0:     if (elts.empty()) { //      return [[]]         return vector<vector<int>>(1, vector<int>());     } //  else:     else { //      smaller = powerset(elts[1:])         vector<vector<int>> allofthem = powerset(             vector<int>(elts.begin() +1, elts.end())); //      elt = [elts[0]]         int elt = elts[0]; // in python elt list (of int) //      withelt = [] //      s in smaller: //          withelt.append(s + elt) //      allofthem = smaller + withelt         const int n = allofthem.size();         (int i=0; i<n; ++i) {             const vector<int>& s = allofthem[i];             allofthem.push_back(s);             allofthem.back().push_back(elt);         } //      return allofthem         return allofthem;     } } 

test code below

int main() {     const int n = 5;     vector<int> input;     for(int i=1; i<=n; ++i) {         input.push_back(i);     }     vector<vector<int>> ps = powerset(input);     for(const vector<int>& set:ps) {         cout << "[ ";         for(int elt: set) {             cout << elt << " ";         }         cout << "]\n";     }     return 0; } 

as footnote, pleasantly surprised how straightforward translate python c++. had read might make sense use python write (or prototype) algorithms, , rewrite in language such c++ necessary, but, proverb goes, seeing believing.

---

here version of program works c++98. reverted basic c++11 features used (>> in template declarations , range-based for).

#include <vector> using std::vector; #include <iostream> using std::cout;  vector<vector<int> > powerset(const vector<int>& elts) {     if (elts.empty()) {         return vector<vector<int> >(1, vector<int>());     }     else {         vector<vector<int> > allofthem = powerset(             vector<int>(elts.begin() +1, elts.end()));         int elt = elts[0];         const int n = allofthem.size();         (int i=0; i<n; ++i) {             const vector<int>& s = allofthem[i];             allofthem.push_back(s);             allofthem.back().push_back(elt);         }         return allofthem;     } }  int main() {     const int n = 5;     vector<int> input;     for(int i=1; i<=n; ++i) {         input.push_back(i);     }     vector<vector<int> > ps = powerset(input);     for(vector<vector<int> >::const_iterator i=ps.begin(); i!=ps.end(); ++i) {         const vector<int>& set = *i;         cout << "[ ";         for(vector<int>::const_iterator j=set.begin(); j!=set.end(); ++j) {             int elt = *j;             cout << elt << " ";         }         cout << "]\n";     }     return 0; }