Generating the powerset in C

Question

I am solving another problem in leetcode.

Given a set, generate all the subsets of the set.

Input: [1,2,3]
Output: [ [3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]

The solution is accepted but I would like to improve on my C coding style. I have created a node_t type to encapsulate the data related each subset. There could be less verbose ways to do this. Two popular methods of solving this problem seem to be:

1. backtracking
2. a subset equals to binary number ≤ n where n is element count.

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


typedef struct node_s {
    int *array;
    int  size;
    struct node_s *next;
} node_t;

node_t* alloc_node()
{
    return (node_t*)malloc(sizeof(node_t));
}

void free_node(node_t *node)
{
    free(node);
}
#define SIZE 3

void print_one(int *one)
{
    printf("%d ", *one);
}
void print_1d_array(int *array, int size)
{
    for(int i = 0; i < size; i++) {
        print_one(&array[i]);
    }
    printf("\n");
}
void print_2d_array(int **array, int *col_sizes, int size)
{
    for (int i = 0; i < size; i++) {
        print_1d_array(array[i], col_sizes[i]);
    }
}
int** create_solution_array(node_t *head, int ans_size, int **column_sizes)
{
    int **ans = (int**)malloc(sizeof(int*)*ans_size);

    node_t *iter;
    iter = head->next;
    int idx = 0;
    while(iter) {
        ans[idx] = iter->array;
        (*column_sizes)[idx] = iter->size;
        idx++;
        iter = iter->next;
    }
    return ans;
}

void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) {
    if (idx == num_size) {
        node_t *new_node = alloc_node();
        if (cur_size) {
            new_node->array = (int *) malloc(sizeof(int) * cur_size);
            new_node->size = cur_size ;
            memcpy(new_node->array, cur, cur_size*sizeof(int));
        }
        (*iter_node)->next = new_node;
        *iter_node = new_node;
        (*ans_size)++;
        return;
    }

    gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
    *(cur + cur_size) = num[idx];
    gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);
}

int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {
    node_t  *head = alloc_node();
    node_t  *iter = head;
    int     *cur = (int*)malloc(sizeof(int)*numsSize);
    gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
    return create_solution_array(head, *returnSize, columnSizes);
}


int main ()
{
    int *nums = (int*)malloc(sizeof(int)*SIZE);
    for (int i = 0; i < SIZE; i++) {
        nums[i] = i+1;
    }
    int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
    int ans_size;
    int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
    print_2d_array(ans, col_sizes, ans_size);
    return 0;
}

Answer 1

I'll just work through this from the top:

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

Looks good; we need these.

---

typedef struct node_s {
    int *array;
    int  size;
    struct node_s *next;
} node_t;

It's usual to use the same structure tag as the typename we're going to use: struct node_t.

If size is the number of elements in the array, a more natural type might be size_t.

---

node_t* alloc_node()
{
    return (node_t*)malloc(sizeof(node_t));
}

All this does is to allocate the memory. Consider initialising the members to sane values, too:

node_t* alloc_node()
{
    node_t *n = malloc(sizeof *n);
    if (n) {
        n->array = NULL;
        n->size = 0;
        n->next = NULL;
    }
    return n;
}

We're writing C, so it's not advised to cast the result of malloc(). But we can't assume it succeeds!

It's a good habit to use the assigned-to variable in the argument of sizeof, rather than its type; that saves us the mental work of having to check that the type actually matches. That's why I've used sizeof *n in place of sizeof (node_t) here; you'll see just following an example where we're further from the declaration and this idiom has more benefit.

It's possibly a good idea to create the array at the same time:

node_t* alloc_node(size_t array_count)
{
    node_t *n = malloc(sizeof *n);
    if (n) {
        n->array = malloc(sizeof *n->array * array_count);
        n->size = n->array ? array_count : 0;
        n->next = NULL;
    }
    return n;
}

---

void free_node(node_t *node)
{
    free(node);
}

Assuming that the node owns its array, we need to free that, too:

void free_node(node_t *node)
{
    if (node) {
        free(node->array);
    }
    free(node);
}

Does the node own its next as well? If so, we need to free that, or perhaps return it.

---

#define SIZE 3

Why is this in the middle here? It should be right at the beginning (or perhaps just before main()).

---

void print_one(int *one)
{
    printf("%d ", *one);
}

I'm not convinced there's much benefit to encapsulating this as a function.

---

void print_1d_array(int *array, int size)
{
    for(int i = 0; i < size; i++) {
        print_one(&array[i]);
    }
    printf("\n");
}

We should use size_t for the count here:

void print_1d_array(int *array, size_t size)
{
    for (size_t i = 0;  i < size;  ++i) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

---

void print_2d_array(int **array, int *col_sizes, int size)
{
    for (int i = 0; i < size; i++) {
        print_1d_array(array[i], col_sizes[i]);
    }
}

Another size_t (okay, I'll stop mentioning these now).

---

int** create_solution_array(node_t *head, int ans_size, int **column_sizes)
{
    int **ans = (int**)malloc(sizeof(int*)*ans_size);

    node_t *iter;
    iter = head->next;
    int idx = 0;
    while(iter) {
        ans[idx] = iter->array;
        (*column_sizes)[idx] = iter->size;
        idx++;
        iter = iter->next;
    }
    return ans;
}

Aside from points from earlier, that while loop has an initialisation and an advancement, so it's really a for loop:

int** create_solution_array(node_t *head, size_t ans_size, size_t **column_sizes)
{
    int **ans = malloc(sizeof *ans * ans_size);

    if (ans) {
        int idx = 0;
        for (node_t *iter = head->next;  iter;  iter = iter->next) {
            ans[idx] = iter->array;
            (*column_sizes)[idx] = iter->size;
            ++idx;
        }
    }
    return ans;
}

---

void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) {
    if (idx == num_size) {
        node_t *new_node = alloc_node();
        if (cur_size) {
            new_node->array = (int *) malloc(sizeof(int) * cur_size);
            new_node->size = cur_size ;
            memcpy(new_node->array, cur, cur_size*sizeof(int));
        }
        (*iter_node)->next = new_node;
        *iter_node = new_node;
        (*ans_size)++;
        return;
    }

    gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);
    *(cur + cur_size) = num[idx];
    gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);
}

*(cur + cur_size) is normally written cur[cur_size].

We need to check whether our allocations succeeded:

/* true if successful, false on any error (e.g. out of memory) */
bool gen_powerset(int *num, size_t num_size, size_t idx,
                  size_t cur_size, int *cur, node_t **iter_node,
                  size_t *ans_size)
{
    if (idx == num_size) {
        node_t *new_node = alloc_node(cur_size);
        if (!new_node || new_node->size != cur_size) {
            return false;
        }
        if (cur_size) {
            memcpy(new_node->array, cur, sizeof *cur * cur_size);
        }
        (*iter_node)->next = new_node;
        *iter_node = new_node;
        ++*ans_size;
        return true;
    }

    cur[cur_size] = num[idx];

    return gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size)
        && gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size);
}

---

int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {
    node_t  *head = alloc_node();
    node_t  *iter = head;
    int     *cur = (int*)malloc(sizeof(int)*numsSize);
    gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);
    return create_solution_array(head, *returnSize, columnSizes);
}

Again, check that malloc() succeeded, and check that gen_powerset() succeeded.

---

int main ()
{
    int *nums = (int*)malloc(sizeof(int)*SIZE);
    for (int i = 0; i < SIZE; i++) {
        nums[i] = i+1;
    }
    int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
    int ans_size;
    int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);
    print_2d_array(ans, col_sizes, ans_size);
    return 0;
}

Having carefully created free_node(), we completely forgot to use it. Valgrind reveals a substantial leak due to this. We need to free the other allocated memory, too.

Answer 2

I subscribe to everything @TobySpeight said.

I also believe that you could make your code a lot clearer (and your coding style better) by obeying a few important rules:

When in doubt, choose the simplest algorithm

Binary representation of numbers between 0 and the size of the powerset are the simplest tool to compute the subsets of the powerset; 0 means the absence, 1 the presence of an element of the initial set:

// {1, 2, 3}
// 000 -> {}
// 001 -> {3}
// 010 -> {2}
// ...
// 111 -> {1,2,3}

Since the size of the powerset is 2^N, where N is the cardinality of the set, and given a function taking the original set and a number to return the subset characterized by this number, a simple array and a simple for loop are enough to achieve our objective:

for (int i = 0; i < pow(2, set.size); ++i)
    powerset[i] = subset(set, i);

That is quite simpler than linked nodes etc.

When in doubt, bundle together what goes together well

Outside of special cases, like the C-string, a pointer without a size won't be of much use to represent a range. So keep the pointer and the size together, rather than having arrays of pointers and arrays of sizes side by side, as in your subsets function:

typedef struct {
  int* items;
  size_t size;
} Set;

typedef struct {
  Set* subsets;
  size_t size;
} Powerset;

Whether you want to fill them, print them, free them, you'll need to have both informations, because you can't deduce one from the other.

A working example:

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

typedef struct {
  int* items;
  size_t size;
} Set;

typedef struct {
  Set* subsets;
  size_t size;
} Powerset;

int is_bit_on(int n, int pos) {
  return (n >> pos) & 1;
}

int set_bits(int n) {
  // any set bits counting function will do fine
  // this one is gcc only
  return __builtin_popcount(n);
  // but you could have to write your own;
  // see https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer
}

Set subset(Set set, int step) {
  int* subset = malloc(sizeof(int) * set_bits(step));
  if (subset == NULL) {
    Set failure = { .items = NULL, .size = 0 };
    return failure;
  }
  int elem_n = 0;
  for (; set.size > 0; --set.size) {
    if (is_bit_on(step, set.size - 1))
      subset[elem_n++] = set.items[set.size-1];
  }
  Set ret = { .items = subset, .size = elem_n };
  return ret;
}

Powerset powerset(Set set) {
  size_t powerset_size = pow(2, set.size);
  Powerset powerset = {
    .subsets = malloc(sizeof(Set) * powerset_size),
    .size  = powerset_size
  };
  Powerset failure = { .subsets = NULL, .size = 0 };
  if (powerset.subsets == NULL) return failure;

  for (size_t i = 0; i < powerset_size; ++i) {
    powerset.subsets[i] = subset(set, i);
    if (powerset.subsets[i].items == NULL) {
      for (size_t j = 0; j < i; ++j) {
        free(powerset.subsets[j].items);
      }
      return failure;
    }
  }
  return powerset;
}

void free_powerset(Powerset powerset) {
  for (size_t i = 0; i < powerset.size; ++i) {
    free(powerset.subsets[i].items);
  }
  free(powerset.subsets);
}

void print_array(Set array) {
  for (size_t i = 0; i < array.size; ++i)
    printf("%d, ", array.items[i]);
  printf("\n");
}


int main(void) {
  int items[] = {1, 2, 3}; 
  Set set = { .items = items, .size = 3};
  Powerset test = powerset(set);

  if (test.subsets == NULL) {
    printf("Bad allocation");
    return 1;
  }

  for (size_t i = 0; i < test.size; ++i)
    print_array(test.subsets[i]);

  free_powerset(test);
  return 0;
}