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