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

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

示例 2：
输入：n = 1
输出：["()"]

先优先填充左括号，把左括号分支的所有可能探索到底，再逐步回溯返回，尝试填充右括号的分支，最终遍历所有合法路径，收集所有有效组合。
思路：
1、定义MAX_SIZE 1430，这是卡特兰数的第 9 项（对应n=8时的有效括号组合数），用来保证结果数组result的内存足够容纳所有可能的组合，避免内存溢出。
2、填充左括号的合法条件：当前已使用的左括号数left < n：
在str的第index位填充左括号'('。
递归调用generate，更新参数：left+1（左括号数加 1）、index+1（下一个填充位置后移一位），其他参数保持不变。
递归深入探索这条路径，直到无法继续填充左括号，或触发终止条件。
递归返回后，无需手动还原str[index]（隐式回溯），后续分支 2 会直接覆盖该位置的值。
3、填充右括号的合法条件：当前已使用的右括号数right < left：
在str的第index位填充右括号')'。
递归调用generate，更新参数：right+1（右括号数加 1）、index+1（下一个填充位置后移一位），其他参数保持不变。
递归深入探索这条路径，直到触发终止条件，或无法继续填充合法括号。
递归返回后，当前层的所有分支执行完毕，继续回溯返回上一层，直到探索完所有合法路径。
4、当index == 2 * n时，说明临时字符串str已经填充了2n个字符（正好是n个左括号和n个右括号），且通过后续的合法分支筛选，这个组合是有效的。此时执行：
为结果数组的当前位置分配内存（长度2n+1），用于存储这个完整的合法组合。
用strcpy将str中的内容复制到结果数组中，然后将*returnSize自增 1（更新有效结果数量）。
执行return，终止当前递归分支，开始回溯返回上一层，尝试其他合法路径。

#define MAX_SIZE 1430

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

char** generateParenthesis(int n, int* returnSize) {
    char *str = (char*)calloc((2 * n + 1), sizeof(char));
    char **result = (char**)malloc(sizeof(char*)*MAX_SIZE);
    *returnSize = 0;
    generate(0, 0, n, str, 0, result, returnSize);
    return result;
}

给大家写一个例子：
还是以n=2为例：n=2，最终要生成2n=4个字符
初始调用：generate(0,0,2,str,0,result,returnSize)（str初始全为'\0'，index=0）
我们分阶段 1：探索左括号到底（生成(())）、阶段 2：递归返回 + 回溯（尝试右括号分支，生成()()）两个阶段来讲。

阶段 1：探索左括号分支，直达终止条件（生成(())）
这是 “去程”，一步步深入递归：
第 1 层（初始层）：left=0, right=0, index=0
满足left < 2，执行str[0]='('，递归调用generate(1,0,2,str,1,...)（去程，进入下一层）
此时str[0]='('，上一层的 “右括号分支”（if(right<left)）还没执行，被暂停了。
第 2 层：left=1, right=0, index=1
满足left < 2，执行str[1]='('，递归调用generate(2,0,2,str,2,...)（去程，进入下一层）
此时str[1]='('，上一层的 “右括号分支” 同样被暂停。
第 3 层：left=2, right=0, index=2
不满足left < 2（左括号已达上限），左括号分支跳过。
满足right < left（0<2），执行str[2]=')'，递归调用generate(2,1,2,str,3,...)（去程，进入下一层）
第 4 层：left=2, right=1, index=3
不满足left < 2，左括号分支跳过。
满足right < left（1<2），执行str[3]=')'，递归调用generate(2,2,2,str,4,...)（去程，进入下一层）
第 5 层：left=2, right=2, index=4
触发终止条件index == 4，将str（此时是"(())"）存入结果数组，returnSize=1。
执行return;，当前层函数执行完毕，开始返回（返程），这是回溯的起点。

阶段 2：递归返回→逐步回溯→尝试未执行的右括号分支（生成()()）
这是重点，我们一步步跟踪 “返程” 和 “尝试其他分支”：
步骤 1：第 5 层返回→回到第 4 层
第 5 层执行return后，回到第 4 层调用generate(2,2,2,str,4,...)的那一行。
第 4 层中，这行递归调用执行完毕，后面没有其他代码了（两个if分支都已执行），因此第 4 层也执行完毕，继续返回→回到第 3 层。
步骤 2：第 4 层返回→回到第 3 层
回到第 3 层调用generate(2,1,2,str,3,...)的那一行。
第 3 层中，这行递归调用执行完毕，后面也没有其他代码了（两个if分支都已执行：左括号跳过，右括号执行完毕），第 3 层执行完毕，继续返回→回到第 2 层。
步骤 3：第 3 层返回→回到第 2 层（首次出现 “未执行的分支”，开始尝试其他路径）
回到第 2 层调用generate(2,0,2,str,2,...)的那一行（这是左括号分支的递归调用）。
第 2 层中，左括号分支的递归已经执行完毕，现在要继续执行后面未执行的代码 —— 也就是右括号分支（if(right<left)），这就是 “尝试其他分支”！
此时第 2 层的状态：left=1, right=0, index=1（注意：这是第 2 层的原始状态，递归返回后，这些参数不会改变，因为参数是值传递）。
满足right < left（0<1），执行str[1]=')'（隐式回溯发生：原来的str[1]='('被直接覆盖为')'，无需手动还原）。
然后递归调用generate(1,1,2,str,2,...)（去程，进入新的分支，探索()...的路径）。
步骤 4：新分支的去程（生成()()）
第 3 层（新分支）：left=1, right=1, index=2
满足left < 2，执行str[2]='('，递归调用generate(2,1,2,str,3,...)（去程）。
第 4 层：left=2, right=1, index=3
不满足left < 2，左括号分支跳过。
满足right < left（1<2），执行str[3]=')'，递归调用generate(2,2,2,str,4,...)（去程）。
第 5 层：left=2, right=2, index=4
触发终止条件，将str（此时是"()()"）存入结果数组，returnSize=2。
执行return;，开始新一轮返程。
步骤 5：新分支的返程→最终回溯到初始层
第 5 层返回→第 4 层→第 3 层→第 2 层，第 2 层的右括号分支执行完毕，没有其他代码，返回→第 1 层。
第 1 层：此时左括号分支的所有递归（包括后续的右括号分支）都已执行完毕，继续执行第 1 层的右括号分支？
不，第 1 层的状态是left=0, right=0，right < left（0<0）不成立，因此右括号分支跳过。
第 1 层的所有代码执行完毕，整个递归过程结束，最终返回结果数组["(())", "()()"]。