目录
题目要求
题目理解以及思路分析
代码分部讲解
第一部分
第二部分
总结
题目要求
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["( ( ( ) ) )","( ( ) ( ) )","( ( ) ) ( )","( ) ( ( ) )","( )( )( )"]
示例 2：
输入：n = 1
输出：["( )"]
提示：
1 <= n <= 8
来源：力扣（LeetCode）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["( ( ( ) ) )","( ( ) ( ) )","( ( ) ) ( )","( ) ( ( ) )","( )( )( )"]
示例 2：
输入：n = 1
输出：["( )"]
提示：
1 <= n <= 8
来源：力扣（LeetCode）
看见这个题是不是突然想起之前讲过的一个 “有效括号” 那一道题，其实二者有一些关系但是又有一些不同。话不多说，本篇正式开始。
题目理解以及思路分析
(一) 养成一个习惯，看见一道题首先要搞清楚问题是什么意思，用到了哪些知识。本题一看感觉无从下手很难，其实拆开看会发现这个题其实就是数学知识。大家应该都学过 排列组合，本题便是用的这个思想，有效的括号我们之前讲过，所以我们知道了什么是有效的括号。因此，本题便有了思路。无非就是我们排列出 2n 长的字符串，然后一个一个判断是不是有效的括号，根据排列组合我们应该清楚这样的 2n 长的字符串会有很多钟的组合。
清楚了问题，我们就来设计思路
(二) 全部排列完后，一个一个去判断。这个思路没问题但是实现起来很麻烦，为了简洁，本篇采用的是 边排边判断 的思路。
(三) 根据括号的有效性我们知道，一个有效的括号一定是从一个 左括号 开始，到一个 右括号 结束。所以我们就用 左括号 去排，如果 左括号 不大于 n ，我们就加一个 左括号；如果 右括号 小于左括号，我们就加一个 右括号。
(四) 知道了怎么排，接下来就是如何判断有效性的问题了，很显然，右括号不能大于左括号(否则无法形成一个有效的括号),其次就是左右括号数量都不能超过 n ，否则判定错误。
看到这相信还有些读者不太清楚，所以我画了下面的图片供大家理解。
明白了这些后，我们进行代码的实战讲解
代码分部讲解
第一部分
#define MAX_SIZE 1430 //卡特兰数
//定义函数
void generate(int left,int right,int n,char *str,int top,char **result,int *returnSize)
{
if(left==n && right==n) //如果左右括号都用完
{
result[(*returnSize)] = (char*)calloc((2 * n + 1), sizeof(char));
strcpy(result[(*returnSize)++], str);
return;
}
if(leftright && right
这一部分是整个代码最核心的部分，所以我会一点一点的讲解。
if(left==n && right==n) //如果左右括号都用完
if(leftright && right
其实主要还是这三个判断的语句
前面讲过，我们采用 边排边判断 的方法。这些都是在最后两个 if 判断语句中实现的，所以这个地方很巧妙的。
两个判断的条件其实就已经将不符合的括号形式排除了，这叫做及时止损，没必要接着往下面去排列，因此便使得运行更简洁、更快。
除了这些，还有一些细节需要大家注意：
result[(*returnSize)] = (char*)calloc((2 * n + 1), sizeof(char));
这里分配空间用的是 calloc 而不是 malloc
calloc比malloc多了一个初始化为0的过程，使用malloc后字符串并不是默认以' '结尾，导致 strcpy(result [ (* returnSize)++ ], str ); 溢出，你需要在 strcpy 前指定字符串str [ top ]=' '
所以推荐使用字符串时使用 calloc 申请内存空间，可以防止不必要的溢出
第二部分
char ** generateParenthesis(int n, int* returnSize){
int top = 0,left = 0,right = 0; //定义声明
char *str = (char*)calloc((2 * n + 1), sizeof(char)); //分配空间
char **result = (char **)malloc(sizeof(char *) * MAX_SIZE); //分配空间
*returnSize = 0; //初始化
generate(0,0,n,str,top,result,returnSize); //调用函数
return result; //返回
}
这一部分就很好理解了，就不过多的叙述了
总结
本题采用的 边排边判断 的方法，使得程序运行的更简洁。其实说白了，根本的算法就是 回溯法 这个经典的算法。本质就是调用函数，进行的递归，排列一种可能，然后回溯接着去排列另一种可能。以此类推便实现了本题的代码。
#define MAX_SIZE 1430 //卡特兰数
//定义函数
void generate(int left,int right,int n,char *str,int top,char **result,int *returnSize)
{
if(left==n && right==n) //如果左右括号都用完
{
result[(*returnSize)] = (char*)calloc((2 * n + 1), sizeof(char));
strcpy(result[(*returnSize)++], str);
return;
}
if(leftright && right
这一部分是整个代码最核心的部分，所以我会一点一点的讲解。
if(left==n && right==n) //如果左右括号都用完
if(leftright && right
其实主要还是这三个判断的语句
前面讲过，我们采用 边排边判断 的方法。这些都是在最后两个 if 判断语句中实现的，所以这个地方很巧妙的。
两个判断的条件其实就已经将不符合的括号形式排除了，这叫做及时止损，没必要接着往下面去排列，因此便使得运行更简洁、更快。
除了这些，还有一些细节需要大家注意：
result[(*returnSize)] = (char*)calloc((2 * n + 1), sizeof(char));
这里分配空间用的是 calloc 而不是 malloc
calloc比malloc多了一个初始化为0的过程，使用malloc后字符串并不是默认以' '结尾，导致 strcpy(result [ (* returnSize)++ ], str ); 溢出，你需要在 strcpy 前指定字符串str [ top ]=' '
所以推荐使用字符串时使用 calloc 申请内存空间，可以防止不必要的溢出
第二部分
char ** generateParenthesis(int n, int* returnSize){
int top = 0,left = 0,right = 0; //定义声明
char *str = (char*)calloc((2 * n + 1), sizeof(char)); //分配空间
char **result = (char **)malloc(sizeof(char *) * MAX_SIZE); //分配空间
*returnSize = 0; //初始化
generate(0,0,n,str,top,result,returnSize); //调用函数
return result; //返回
}
这一部分就很好理解了，就不过多的叙述了
总结
本题采用的 边排边判断 的方法，使得程序运行的更简洁。其实说白了，根本的算法就是 回溯法 这个经典的算法。本质就是调用函数，进行的递归，排列一种可能，然后回溯接着去排列另一种可能。以此类推便实现了本题的代码。
