# Printing all subsets

I have tried to incorporate comments from my previous code review into this. So, I am hoping for less mistakes. If you spot any, please let me know mercilessly!

#include <iostream>
#include <queue>

void printsub(int* p, int len, std::queue<int> q) {

if (!len) {
while(!q.empty()) {
std::cout << q.front() << " ";
q.pop();
}
std::cout << "\n";
return;
}

std::queue<int> t1(q);
t1.push(p[0]);
printsub(&(p[1]), len - 1, t1);

std::queue<int> t2(q);
printsub(&(p[1]), len - 1, t2);
}

int main() {
int arr[] = {1, 2, 3, 4, 5, 6};

std::queue<int> q;
printsub(arr, ((sizeof(arr))/(sizeof(arr[0]))), q);
}

• Not enough for an answer but consider whether if(!len) makes sense. You are treating a number as a boolean value and while C++ allows this due to weak typing, it’s not a meaningful operation. Change it to an explicit check, if (len != 0). – Konrad Rudolph Jun 12 '12 at 10:29

You could translate this recursive Python code.

def xcombinations(items, n):
if n==0: yield []
else:
for i in xrange(len(items)):
for cc in xcombinations(items[:i]+items[i+1:],n-1):
yield [items[i]]+cc


in C++ roughly (untested, but you get the idea):

using std::set;

set<set<int>> xcombinations(const set<int> &items, size_t n) {
set<set<int>> result; // collect for 'return' instead of pythons 'yield'
if(n==0) return result;
for(int elem : items) { // ranged-for from C++11
// 'items' without 'elem', python 'items[:i]+items[i+1:]'
set<int> temp(items); // copy
temp.erase(elem); // ...or use 'std::remove_copy_if'
for(auto cc : xcombinations(temp, n-1)) { // ranged-for from C++11
cc.insert(elem);
result.insert(cc); // python yield;
}
}
return result;
}


Note that auto cc creates a copy in the inner loop, where one can add elem before adding it to result.

Instead if the new C++11 ranged-for and auto one can of course just use lengthy iterator-based for-loops.

Using vector instead of set would also work, I guess. There are no set-operations involved here. Actually, now that I think of it, vector would be much better... hmm...

One could save some copying by pulling temp out of the loop, initialize it with a a size of n-1 and use std::remove_copy_if to put the values into it. And if one does that, one can even save the copy of all values by just replacing one in the inner loop, but I can not see how right away.

Ah, well and you need a printing routine, of course.

std::ostream& operator<<(std::ostream &os, const set<int>& items) {
for(int elem: items)
os << elem << " ";
return os;
}
std::ostream operator<<(std::ostream &os, const set<set<int>>& itemss) {
for(const auto &cc: itemss)
os << "  {" << cc << "}\n";  // or use 'ostream_iterator' on 'cc'
return os;
}

int main(/*...*/) {
set<int> data = {1, 2, 3, 4, 5, 6}; // C++11 init-list
std::cout << xcombinations(data, data.size()) << std::endl;
}