LeetCode 22. 括号生成

22. 括号生成

难度中等

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

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]
思路：可以用树将示例模拟一遍，如下图（有点丑，不用吐槽，我承认，傲娇脸），我们可以通过递归进行，向左是添加左括号，向右添加右括号，为了是括号匹配，有括号的数量不能多于左括号的数量，还有就是输入的括号可以当作是一个字符串，所以我们要记得在最后加上''。

代码如下：

 1 /**
 2  * Note: The returned array must be malloced, assume caller calls free().
 3  */
 4 void dfs(char* temp,int index,int left,int right,char** result,int* count,int n)
 5 {
 6     if(left==0&&right==0){
 7         result[(*count)]=(char*)malloc((2*n+1)*sizeof(char));
 8         strcpy(result[(*count)++],temp);
 9         return ;
10     }
11     temp[index+1]='';
12     if(left>0){
13         temp[index]='(';
14         dfs(temp,index+1,left-1,right,result,count,n);
15     }
16     if(right>left){
17         temp[index]=')';
18         dfs(temp,index+1,left,right-1,result,count,n);
19     }
20 }
21 
22 
23 char ** generateParenthesis(int n, int* returnSize){
24     char** result;
25     char* temp;
26     result=(char **)malloc(2000*sizeof(char*));
27     temp=(char *)malloc((2*n+1)*sizeof(char));
28     int left=n,right=n,index=0,count=0;
29     dfs(temp,index,left,right,result,&count,n);
30     *returnSize=count;
31     return result;
32 }