Exercise: Subsets

The previous exercise, where I asked you to reverse the input recursively, showed how a recursive function can store variables, and how each invocation of the recursive function has its own local variables. And yet, in that example we never made more than one recursive call from each function.

Here, we'll make two! I will ask you to print all subsets of a set of numbers {1, ..., N}. For example, for {1, 2, 3}, there are 8 subsets, shown here without commas to make it easier to print:

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

The last one is the empty set, which we also consider a subset of any set.

If our set has N elements, there will be 2^N subsets. Indeed, we can either take the first element to our subset, or skip it, this gives us 2 options. For each of those options, we can either take or skip the second element, so we have 4 options now. With the third element, taking it or skipping it gives us 8 options, and so on; for N elements there will be 2^N options.

How can we print them all? We'll use recursion!

Note: there is a fun way of generating subsets using bit operations, I'm mentioning it here just in case if you came on this page to find it. We haven't talked about bit operations yet, I will show how to use them to print all subsets later!

Assuming that N is not greater than 10, let's create an array int take[11] of boolean flags, 0 or 1, where 0 in take[i] means that the corresponding number i is not in our subset, and 1 means that it is taken. Note that array indexing starts from 0, so I'm just allocating one more element to make sure take[N] exists; we will never use take[0].

The recursive function will accept this array, the maximum number in our set, and the current position:

void subsets(int *take, int n, int pos) {
  ...
}

First things first: when should we stop? If the current position pos is greater than n, we have a valid subset defined in take, so we print it. That's our base case.

But if pos is less then N, we have two options: we can either take element pos, setting take[pos] = 1, or skip it, setting take[pos] = 0. In each case, we should call our recursive function for the next position. That way, subsets(take, n, 1) will call subset(take, n, 2) twice (with different values of take[1]), each of them will call subset(take, n, 3) twice, and so on.

Ready to write this function? I'll implement the print function for you:

#include <stdio.h>

/* A function to print a subset: use it from subset() */
void print(int *take, int n) {
	int i;
	printf("{");
  for (int i = 1; i <= n; ++i) {
    if (take[i]) {
      printf(" %d", i);
    }
  }
  printf(" }\n");
}

/* The main recursive function: implement it! */
void subsets(int *take, int n, int pos) {
  /* TODO: write the code */
}

int main() {
	int N;
  int take[11]; /* assuming N <= 10 */
  scanf("%d", &N);
  subsets(take, N, 1);
  return 0;
}

Try figuring this out, and then we'll have one more exercise on recursion!