#include <iostream>
using namespace std;

const int MSIZE = 1000;

class Node {

  public:
   Node(int x) {
    key = x;
    next = 0;
  }

  public:
     int key;
     Node* next;
 };

class List {

public:
List() {
  head = 0;
}

List(int x) {
 head = new Node(x);
}

List(Node* n) {
 head = n;
}

void insert(int k) {
 // insert k as the first item of the list
 Node* tmp = new Node(k);
 tmp->next = head;
 head = tmp;
 }

List* copy() {
 Node* tmp = nodecopy(head);
 List* tmp1 = new List(tmp);
 return tmp1;
}

void print() {
 Node* temp = head;
 cout << "{";
 while (temp != 0) {
  cout << temp->key;
  if (temp->next!= 0) cout << ", ";
  temp = temp->next;
  }
  cout << "}";
  cout << endl;
 }

 public:
 Node* head;
};

class set {

public:
List* mems[MSIZE];
int current; // current number of lists filled

public:
set(int n) {
  for (int j=0; j < n; ++j)
   mems[j] = 0;
  current = n;
}


void print() {
 for (int j = 0; j < current; ++j)
   mems[j]->print();
 }

static set merge(set L1, set L2) {
  // performs the union of sets L1 and L2
 int s1 = L1.current;
 int s2 = L2.current; int s = s1 + s2;
 set tmp(s);
 for (int i = 0; i < s1; ++i)
   tmp.mems[i] = L1.mems[i];
 for (int i = 0; i < s2; ++i)
   tmp.mems[s1+i] = L2.mems[i];
 return tmp;
 }

static set copy(set L) {
// makes a copy of set L1 and returns the copied set
int j = L.current;
set tmp(j);
for (int i = 0; i < j; ++i) 
  tmp.mems[i] = L.mems[i]->copy();
return tmp;
}

static set build(int a[], int s) {
 // build all subsets of {1, 2, ... , s} as an array of lists.
 // assume that s <= a.length
 if (s == 0) {
	 set x(1);
	 x.mems[0] = new List();
	 x.current = 1; return x;
   }
 else if (s == 1) {
   set x(2);
   x.mems[0] = new List();
   x.mems[1] = new List(a[0]); x.current = 2; return x;
  }
 else
  {
   set L1 = build(a,s-1);
   set L2 = copy(L1);  // copying will be more efficient
   int pow = L2.current;
   for (int k = 0; k < pow; ++k)
    L2.mems[k]->insert(a[s-1]);
   set L = merge(L1, L2);
   return L;
  }
 }
};

int main() {
 int s;
 cout << "Enter the size of the set." << endl;
 cin >> s;
 int a[s];
 if (s!= 0)
   cout << "Enter the elements of the set." << endl;
 for (int j=0; j < s; ++j)
   cin >> a[j];
 set temp = set::build(a, s);
 cout << "The subsets are: " << endl;
 temp.print();
 }