---

题目

链接: https://leetcode.cn/problems/generate-parentheses/description/

思路

我们可以通过回溯递归算法求解
如果左括号数量不大于n，我们可以放一个左括号。
如果右括号数量小于左括号的数量，我们可以放一个右括号。

用 str 来记录每一个元素

对于递归我们可以利用这样一个方法函数 generate

我们可以粗略地把这个过程理解为下图

然后我们时不断在右边添加左括号或右括号的，所以在调用 generate 时需要借用一个索引 index

---

代码实现

需要注意的是下面代码中元素 str 创建时用的是 calloc 并且还多创建了一个空间原因是在赋值给 result 时用的是 strcpy 它是以尾部地0判断结束的，而 calloc 中的每一个元素都为0，
如果要用 malloc 必须手动在末尾添加上一个0来做结束
也可以改变读取方式，不用 strcpy ，用循环赋值的方法也是一样的

void generate(int left, int right, int n, char* str, int index, char** result,
              int* returnSize) {
    if (index == 2 * n) {
        result[(*returnSize)] = (char*)calloc((2 * n + 1), sizeof(char));
        strcpy(result[(*returnSize)++], str);
        return;
    }
    // 最多放n个左括号，如果左括号数量不大于 n，可以放一个左括号
    if (left < n) {
        str[index] = '(';
        generate(left + 1, right, n, str, index + 1, result, returnSize);
    }
    // 右括号只能放左括号右边，不能先放右括号如果右括号数量小于左括号的数量，可以放一个右括号
    if (right < left) {
        str[index] = ')';
        generate(left, right + 1, n, str, index + 1, result, returnSize);
    }
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char** generateParenthesis(int n, int* returnSize) {
    char* str = (char*)calloc((2 * n + 1), sizeof(char));
    char** result =
        (char**)malloc(sizeof(char*) * 1430); // n最大为8时的元素个数
    *returnSize = 0;
    generate(0, 0, n, str, 0, result, returnSize);
    return result;
}