/************************************************
Algorithmen und Problemloesungen mit C++,
http://www.algorithmen-und-problemloesungen.de
Copyright @2007 by Doina Logofatu
************************************************/

#include <fstream>
#include <iostream>
#include <vector>

using namespace std;
void write(unsigned n, vector<bool> &b, ofstream &out){
  unsigned i, nr1 = 0;
  for(i=0; i<n; i++){
    if(b[i]){
      nr1++;
      if(1==nr1){
        out<< "{" << i+1;
      } else {
          out << ", " << i+1;
      }
    }
  }
  if(nr1>0) out << "}" << endl;
  else out << "{}" << endl;
}

vector<bool> giveGrayCode(vector<bool> &b){
  vector<bool> vRet;
  short n = (short)b.size();
  for(short i=0; i<n-1; i++) 
    vRet.push_back((bool)((b[i]+b[i+1])%2));
  vRet.push_back(b[n-1]);
  return vRet;
}

int main(){
  vector<bool> b, c;
  short n, k, i;
  bool flag;
  ofstream out("subsets.out");
  cout<< " n = "; cin >> n;
  flag=true;
  for(i=0; i<n; i++) b.push_back(0);
  while(flag){
    k=0;   
    c = giveGrayCode(b);
    write(n, c, out);
    while(k<n && 1==b[k]) b[k++]=0;
    if(k<n)      
      b[k]=1;
    else
      flag = false;    
  } 
  return 0;   
}