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


/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

void build(int f_s, int f_e, char *pat, char **buf, int *buf_n, int *i, int n) {
    int skip = n * 2 + 1;
    if (strlen(pat) == n * 2) {
        if (*i >= *buf_n) {
            *buf_n *= 2;
            *buf = realloc(*buf, *buf_n * skip * sizeof(char));
        }
        strcpy(*buf + *i * skip, pat); 
        ++(*i);
        return;
    }
    char *tmp = malloc(skip * sizeof(char));
    strcpy(tmp, "()");
    strcpy(tmp + 2, pat);
    build(1, f_e, tmp, buf, buf_n, i, n);

    strcpy(tmp, "(");
    strcat(tmp, pat);
    strcat(tmp, ")");

    build(0, 0, tmp, buf, buf_n, i, n);

    if (! f_s && ! f_e) {
        strcpy(tmp, pat);
        strcat(tmp, "()");
        build(f_s, 1, tmp, buf, buf_n, i, n);
    }
    free(tmp);
}


char** generateParenthesis(int n, int* returnSize) {
    int skip = n * 2 + 1;
    int buf_n = 10, i = 0;
    char *pat = malloc(skip * sizeof(char));
    char *buf = malloc(skip * buf_n * sizeof(char));
    strcat(pat, "()");
    build(1, 1, pat, &buf, &buf_n, &i, n);
    char **words = malloc(sizeof(char *) * i);
    for (int w = 0; w != i; ++w) 
        words[w] = strdup(buf + skip * w);
    free(buf);
    free(pat);
    *returnSize = i;
    return words;
}