22括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/generate-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

动态规划
执行用时：16 ms
内存消耗：17.4 MB

char **dynamicGen(int len, int x, int y, int *returnSize)
{
    int size_1 = 0, size_2 = 0;
    char **arr_1 = NULL, **arr_2 = NULL;
    char **result = NULL;
    int i = 0;
    if (x < y || x < 0 || y < 0)
    {
        *returnSize = 0;
        return NULL;
    }
    if (x == 0 && y == 0)
    {
        *returnSize = 1;
        result = malloc(sizeof(char *));
        *result = calloc(len * sizeof(char), sizeof(char));
        return result;
    }
    arr_1 = dynamicGen(len, x - 1, y, &size_1);
    arr_2 = dynamicGen(len, x, y - 1, &size_2);
    *returnSize = size_1 + size_2;
    result = malloc((size_1 + size_2) * sizeof(char *));
    for (i = 0; i < size_1; i++)
    {
        result[i] = arr_1[i];
        result[i][x + y - 1] = '(';
    }
    for (i = size_1; i < size_1 + size_2; i++)
    {
        result[i] = arr_2[i - size_1];
        result[i][x + y - 1] = ')';
    }
    free(arr_1);
    free(arr_2);
    return result;
}

char **generateParenthesis(int n, int *returnSize)
{
    return dfs(n, n, returnSize);
}

Solution 2

回溯法
执行用时：0 ms
内存消耗：12.7 MB

void backtrack(char *s, int *len_s, int left, int right, int n, char **arrays, int *returnSize)
{
    if (*len_s == 2 * n)
    {
        arrays[(*returnSize)++] = strdup(s);
    }
    if (left < n)
    {
        s[(*len_s)++] = '(';
        backtrack(s, len_s, left + 1, right, n, arrays, returnSize);
        (*len_s)--;
    }
    if (right < left)
    {
        s[(*len_s)++] = ')';
        backtrack(s, len_s, left, right + 1, n, arrays, returnSize);
        (*len_s)--;
    }
}

char **generateParenthesis(int n, int *returnSize)
{
    *returnSize = 0;
    int MAX_ARR_NUM = 2000;
    char *s = calloc((2 * n + 1) * sizeof(char), sizeof(char));
    int len_s = 0;
    char **arrays = calloc(MAX_ARR_NUM * sizeof(char *), sizeof(char *));
    backtrack(s, &len_s, 0, 0, n, arrays, returnSize);
    return arrays;
}