#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 20

/* A: array storing flags whether elements are included
   n: total number of elements
   i: decision taken for how many elements
   c: count of the subsets printed so far
*/
int subsets1 ( int A[], int n, int i, int c )
{
   int j, k;

   if (i == n) {
      ++c; printf("Subset No. %3d: ", c);
      k = 0;
      for (j=0; j<n; ++j) if (A[j]) ++k;
      if (k == 0) printf("{}\n");
      else {
         printf("{");
         for (j=0; j<n; ++j) if (A[j]) {
            --k;
            printf("%d%s", j, (k) ? "," : "}\n");
         }
      }
      return c;
   }

   A[i] = 0; c = subsets1(A,n,i+1,c);
   A[i] = 1; c = subsets1(A,n,i+1,c);

   return c;
}

/* A: array storing flags whether elements are included
   n: total number of elements
   i: decision taken for how many elements
   c: count of the subsets printed so far
*/
int subsets2 ( int A[], int n, int i, int c )
{
   int j, k;

   ++c; printf("Subset No. %3d: ", c);
   k = 0;
   for (j=0; j<n; ++j) if (A[j]) ++k;
   if (k == 0) printf("{}\n");
   else {
      printf("{");
      for (j=0; j<n; ++j) if (A[j]) {
         --k;
         printf("%d%s", j, (k) ? "," : "}\n");
      }
   }

   for (j = i; j < n; ++j) {
      A[j] = 1;
      c = subsets2(A,n,j+1,c);
      A[j] = 0;
   }

   return c;
}

/* A: array storing the elements that are included
   n: total number of elements
   i: how many elements are chosen already
   c: count of the subsets printed so far
*/
int subsets3 ( int A[], int n, int i, int c )
{
   int j, k;

   ++c; printf("Subset No. %3d: ", c);
   printf("{");
   for (j=0; j<i; ++j) printf("%s%d", (j) ? "," : "", A[j]);
   printf("}\n");

   k = (i == 0) ? 0 : A[i-1] + 1; 
   while (k < n) {
      A[i] = k; c = subsets3(A,n,i+1,c);
      ++k;
   }

   return c;
}

/* An iterative implementation */
int subsets4 ( int n )
{
   int c = 0, j, first;

   for (c = 0; c < (1U << n); ++c) {
      first = 1;
      printf("Subset No. %3d: {", c+1);
      for (j = 0; j < n; ++j) if (c & (1U << j)) {
         if (!first) printf(",");
         printf("%d",j);
         first = 0;
      }
      printf("}\n");
   }

   return c;
}

/* Another iterative implementation in which recursion is replaced by an
   explicitly managed stack */
int subsets5 ( int n )
{
   int S[MAX_SIZE], top, c, i;
   int printed = 0;

   printf("Subset No.   1: {}\n"); c = 1;
   S[0] = 0; top = 0;
   while (top > -1) {
      if (!printed) {
         ++c; printf("Subset No. %3d: {", c);
         for (i=0; i<=top; ++i) printf("%s%d", (i) ? "," : "", S[i]);
         printf("}\n");
         printed = 1;
      } else if (S[top] == n-1) {
         --top;
         if (top >= 0) ++S[top]; printed = 0;
      } else {
         ++top; S[top] = S[top-1] + 1; printed = 0;
      }
   }

  return c;
}

int main ()
{
   int n, i, c;
   int A[MAX_SIZE];

   printf("n = "); scanf("%d", &n);

   printf("\n+++ Method 1\n");
   for (i=0; i<n; ++i) A[i] = 0;
   c = subsets1(A,n,0,0);
   printf("Number of subsets = %d\n", c);

   printf("\n+++ Method 2\n");
   for (i=0; i<n; ++i) A[i] = 0;
   c = subsets2(A,n,0,0);
   printf("Number of subsets = %d\n", c);

   printf("\n+++ Method 3\n");
   for (i=0; i<n; ++i) A[i] = 0;
   c = subsets3(A,n,0,0);
   printf("Number of subsets = %d\n", c);

   printf("\n+++ Method 4\n");
   c = subsets4(n);
   printf("Number of subsets = %d\n", c);

   printf("\n+++ Method 5\n");
   c = subsets5(n);
   printf("Number of subsets = %d\n", c);

   exit(0);
}