[力扣_22] 括号生成

题目入口：点击进入

相关算法：

• DFS(深度优先搜索)

• BFS(广度优先搜索)——这种解法我分析不来......

思路和算法：

这题由于用C刷的，所以BFS只提供思路，代码写起来需要构造hash，申请空间，构造辅助队列，然后去重，很繁琐，又由于近期任务繁重，并无过多时间去深究，广搜的思路会写到下面，用Java实现起来很容易，但是相对于这题，还是深搜好用

DFS

这一类问题是在一棵隐式的树上求解，可以用深度优先遍历，也可以用广度优先遍历。 一般用深度优先遍历。原因是：

• 代码好写，使用递归的方法，直接借助系统栈完成状态的转移；
• 广度优先遍历得自己编写结点类和借助队列。

这里的「状态」是指程序执行到 隐式树 的某个结点的语言描述，在程序中用不同的 变量 加以区分。

题解思路来自：liweiwei1419

我们以n=2为例，每次的递归都会有两种选择，我们可以知道，序列正确的点在于：

• 右括号数<=左括号数(这里的<=是先小于，界限在等于)
• 左括号数<=n，(原因在于左右括号的序列总长要等于2*n)

画图以后，可以分析出的结论：

• 当前左右括号都有大于 0个可以使用的时候，才产生分支；
• 产生左分支的时候，只看当前是否还有左括号可以使用；
• 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候(右括数必须在右括号数小于左括号数时)，才可以产生分支；
• 在左边和右边剩余的括号数都等于 0(总长度为2*n)的时候结算。

代码如下所示：

void dfs(int left,int right,int max,char *temp,int *returnSize,char **ReturnStr,int len)
{
     if((left+right)==2*max)
     {
      *(ReturnStr+(*returnSize))=(char*)malloc(sizeof(char)*(2*max+1));
      temp[2*max]='\0';
      strcpy(ReturnStr[*returnSize],temp);
      (*returnSize)++;
      return ;
     }
     else
     {
       if(left < max)
       {
          temp[len]='(';
          dfs(left+1,right,max,temp,returnSize,ReturnStr,len+1);
       }
       if(right<left)
       {
          temp[len]=')';
          dfs(left,right+1,max,temp,returnSize,ReturnStr,len+1);
       }
     }
}

char ** generateParenthesis(int n, int* returnSize){
   *returnSize=0;
   if(n==0)
       return NULL;
    char **ReturnStr=(char**)malloc(sizeof(char*)*10000);
    char*temp=(char*)malloc(sizeof(char)*(2*n+1));
    dfs(0,0,n,temp,returnSize,ReturnStr,0);
    return ReturnStr;
}

本文链接：