/*
 * @lc app=leetcode.cn id=22 lang=c
 *
 * [22] 括号生成
 */

// @lc code=start
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#include <string.h>

static void dfs(int n, int left, int right, char *stack, int len, char **results, int *count)
{
    if (len == 2 * n)
    {
        results[(*count)] = malloc((len + 1) * sizeof(char));
        strcpy(results[(*count)++], stack);
        return;
    }
    if (left < n)
    {
        stack[len] = '(';
        dfs(n, left + 1, right, stack, len + 1, results, count);
    }
    if (right < left)
    {
        stack[len] = ')';
        dfs(n, left, right + 1, stack, len + 1, results, count);
    }
}

char **generateParenthesis(int n, int *returnSize)
{
    char *stack = calloc(2 * n + 1, sizeof(char)); // calloc会自动将所分配的内存全部初始化为0，malloc()不会对内存进行初始化，如果想要初始化为0，还要额外调用memset()函数。
    char **parentheses = malloc(5000 * sizeof(char));
    *returnSize = 0;
    dfs(n, 0, 0, stack, 0, parentheses, returnSize);

    return parentheses;
}
// @lc code=end