Creating all subsets recursively without using array

Question

We get non negative integer number n from user and we must print all subsets of set ({1,2,3,...,n}). (n<=20)

for example for n=3 we must print:

{1 , 2 , 3}
{1 , 2}
{1 , 3}
{1}
{2 , 3}
{2}
{3}
{}

,s are optional and the sequence can be printed without any comma. (like {1 2 3}) I must add that the sequence of subsets must be exactly like the example. Meaning first the subsets that have 1, then subsets that have 2 and .... The longest subset must be printed first. (lexicographical from the largest subset (the set itself) to null set)

I see a lot of codes in the Internet that solve this problem with arrays or using a bit array that indicate whether we use a number or not. The issue is that in this question, we are not allowed to use -any- type of array or other data structures like vector ,etc. Even using the array behaviour of something like string is completely prohibited. It must be solved only with recursion.

We are also not allowed to use any advanced functions. For example if we write it with C, we are allowed just to use stdio.h or for C++, only <iostream> is allowed and no other library.

I don't know how to do this without any arrays. How to check which number it must print and at the sametime, manage the {}.

PS1. The question is simply generation powerset with these conditions:

USING ARRAY, STRING AND EVEN LOOPS ARE COMPLETELY PROHIBITED. JUST RECURSION.

User Kosyr submitted a very good answer with bit operators. So if you want to submit another answer, submit an answer that even doesn't use bit operators.

PS2.

I write this code by help of George but it doesn't works fine. It doesn't have something like 1 2 4. It also repeats some cases.

#include <stdio.h>


void printAllSets (int size)
  {printRows (size, 1);}

void printRows (int size , int start)
{
  if (start<=size)
  {printf( "{ ");
  printRow (start, size);
  printf ("}");
  printf ("\n");}
  if (start <= size)
  {printRows(size -1 , start);
    printRows (size , (start + 1));}
}
printRow (int start, int limit)
{

  if (start <= limit)
  {

    printf ("%d ",start);
    printRow (start +1, limit);
  }
}


int main()
{
    printAllSets(5);
    printf("{ }");
    return 0;
}

PS3.

User Kosyr submitted a very good answer with bit operators. So if you want to submit another answer, submit an answer that even doesn't use bit operators.

Answer 1

Recursive algorithms are very memory intensive. Here algorithm for n <= 31

#include <iostream>

void bin(unsigned bit, unsigned k, unsigned max_bits) {
    if (bit == max_bits) {
        std::cout << "{";
        bin(bit - 1, k, max_bits);
    }
    else {
        if ((k & (1u << bit)) != 0) {
            std::cout << (max_bits - bit) << " ";
        }
        if (bit != 0) {
            bin(bit - 1, k, max_bits);
        }
        else {
            std::cout << "}" << std::endl;
        }
    }
}

void print(unsigned k, unsigned n, unsigned max_bits) {
    bin(max_bits, k, max_bits);
    if (k != 0) {
        print(k - 1, n, max_bits);
    }
}

int main()
{
    unsigned n;
    std::cin >> n;
    print((1u << n) - 1u, 1u<<n, n);
    return 0;
}

First recursion print enumerates k from 2^n-1 to 0, second recursion bin enumerates all bits of k and print non-zero bits. For example, max_bits = 5 and k = 19 is 10011b = 16 + 2 + 1 = 2^4 + 2^1 + 2^0, bits 4,1,0 interoperate as set {5-4,5-1,5-0} => {1,4,5}