数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))", "(()())", "(())()", "()(())", "()()()"]
示例 2：
输入：n = 1
输出：["()"]
可以用暴力法先把所有的可能列举出来然后再用括号匹配算法判断是否正确，但时间复杂度太高。
就是不停选括号，要么选左括号，要么选右括号。
并有这些约束的：
只要(有剩，就可以选(。(((((这么选，都还不能判定为非法。
当剩下的)比(多时，才可以选)，否则，)不能选，选了就非法。
因为：剩下的)比(少，即，使用的)比(多，不能成双成对。
描述节点的状态有：当前构建的字符串，和左右括号所剩的数量。
选择
在这里，每次最多两个选择，选左括号或右括号，“选择”会展开出一棵解的空间树。
用 DFS 遍历这棵树，找出所有的解，这个过程叫回溯。
约束条件
即，什么情况下可以选左括号，什么情况下可以选右括号。
利用约束做“剪枝”，即，去掉不会产生解的选项，即，剪去不会通往合法解的分支。
比如()，现在左右括号各剩一个，再选)就成了())，不能让这个错的选择成为选项（不落入递归）：
if (right > left) { // 右括号剩的比较多，才能选右括号
dfs(str + ')', left, right - 1);
}
目标
构建出一个用尽 n 对括号的合法括号串。
意味着，当构建的长度达到 2 * n，就可以结束递归（不用继续选了）。
#define _CRT_SECURE_NO_WARNINGS #include#include #include #include void generate(int left,int right,int size,char* str,int n, int* returnSize,char** result) //left代表左括号数量，right代表右括号数量，str代表储存几组有效组合，returnsize表示返回数量 { if (size == 2 * n) { // 当前长度已达2n result[(*returnSize)] = (char*)calloc((2 * n + 1), sizeof(char)); strcpy(result[(*returnSize)++], str); return; } // 如果左括号数量不大于 n，可以放一个左括号 if (left < n) { str[size] = '('; generate(left + 1, right, size + 1, str, n, returnSize, result); } // 如果右括号数量小于左括号的数量，可以放一个右括号 if (right < left) { str[size] = ')'; generate(left , right+1, size + 1, str, n, returnSize, result); } } char ** generateParenthesis(int n, int* returnSize) { char *str = (char*)calloc((2 * n + 1), sizeof(char)); char **result = (char**)malloc(sizeof(char*) * 1430); // 卡特兰数: 1, 2, 5, 14, 42, 132, 429, 1430，题目中最多生成1430组 *returnSize = 0; generate(0, 0, 0, str, n, returnSize, result); return result; }
