Generating the powerset in C 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:


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




#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;


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 &lt; size; i++) {
        print_one(&amp;array[i]);
    }
    printf("\n");
}
void print_2d_array(int **array, int *col_sizes, int size)
{
    for (int i = 0; i &lt; 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-&gt;next;
    int idx = 0;
    while(iter) {
        ans[idx] = iter-&gt;array;
        (*column_sizes)[idx] = iter-&gt;size;
        idx++;
        iter = iter-&gt;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-&gt;array = (int *) malloc(sizeof(int) * cur_size);
            new_node-&gt;size = cur_size ;
            memcpy(new_node-&gt;array, cur, cur_size*sizeof(int));
        }
        (*iter_node)-&gt;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, &amp;iter, returnSize);
    return create_solution_array(head, *returnSize, columnSizes);
}


int main ()
{
    int *nums = (int*)malloc(sizeof(int)*SIZE);
    for (int i = 0; i &lt; SIZE; i++) {
        nums[i] = i+1;
    }
    int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
    int ans_size;
    int ** ans = subsets(nums, SIZE, &amp;col_sizes, &amp;ans_size);
    print_2d_array(ans, col_sizes, ans_size);
    return 0;
}
I'll just work through this from the top:


#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;



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-&gt;array = NULL;
        n-&gt;size = 0;
        n-&gt;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-&gt;array = malloc(sizeof *n-&gt;array * array_count);
        n-&gt;size = n-&gt;array ? array_count : 0;
        n-&gt;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-&gt;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 &lt; size; i++) {
        print_one(&amp;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 &lt; size;  ++i) {
        printf("%d ", array[i]);
    }
    printf("\n");
}





void print_2d_array(int **array, int *col_sizes, int size)
{
    for (int i = 0; i &lt; 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-&gt;next;
    int idx = 0;
    while(iter) {
        ans[idx] = iter-&gt;array;
        (*column_sizes)[idx] = iter-&gt;size;
        idx++;
        iter = iter-&gt;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-&gt;next;  iter;  iter = iter-&gt;next) {
            ans[idx] = iter-&gt;array;
            (*column_sizes)[idx] = iter-&gt;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-&gt;array = (int *) malloc(sizeof(int) * cur_size);
            new_node-&gt;size = cur_size ;
            memcpy(new_node-&gt;array, cur, cur_size*sizeof(int));
        }
        (*iter_node)-&gt;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-&gt;size != cur_size) {
            return false;
        }
        if (cur_size) {
            memcpy(new_node-&gt;array, cur, sizeof *cur * cur_size);
        }
        (*iter_node)-&gt;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)
        &amp;&amp; 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, &amp;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 &lt; SIZE; i++) {
        nums[i] = i+1;
    }
    int *col_sizes = (int*)malloc(sizeof(int)*SIZE);
    int ans_size;
    int ** ans = subsets(nums, SIZE, &amp;col_sizes, &amp;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.