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;
}

• wispymisty: @Toby Speight Added problem description.

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.

• wispymisty: Thanks @Toby Speight, I am rewriting the solutions with your pointers in mind and comparing how close. I have come across most of the points that you have mentioned but, in practice, they didn't come out in force. I think it will be help to slow down a bit and savor every line I write.

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;
}

• Edward: Good solution, but it’s worth noting that it’s limited to sets no larger than the size of an int.
• papagaga: @Edward Indeed, but this is an acceptable limitation since a set of 32 elements already has a power set of 2^32 elements, i.e more than 4 billions elements, which would take a good time to print...
• wispymisty: Thanks papagaga. I have less experience using builtin functions. I think it is better to use those as they are fully blessed by relevant compilers ? I also like the fact that you are using inline struct initialization. That is really convenient and descriptive. Need to have an arsenal of "when-in-doubt" techniques ingrained in me. Yesterday, I was thinking of how to do inline initialization of function pointer or action based on a type field in type hierarchy. Just want to add some form of reflections with minimal effort. Thanks again for your answer. I will also subscribe to @Toby Speight.
• Toby Speight: If you wanted to deal with sets containing more than 15 elements (where did you get 32 from?), then you could use one of the fixed-size unsigned types from <stdint.h>, of course.