题解 | #括号生成#

题目：括号的生成

描述：给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为："((()))", "(()())", "(())()", "()()()", "()(())",

示例1：输入：1，返回值：["()"]；

示例2：输入：2，返回值：["(())","()()"]

解法一：

思路分析：分析题目，我们可以得到，题目的要求为当输入n对括号后，输出所有由n对括号组成的合法组合，这就意味着，当“（”出现的时候，后序必须要有与之配对的“）”存在，首先我们可以设定一个容器对象vector用于存储最终的结果值，设定一个string类型的变量用于存储括号的对数，设定两个变量值分别为i和j，用于监督此刻需要的“（”或者“）”。

其中i和j的值主要分为五种情况，我们一一进行分析（首先定义i和j的值均为n）：

第一种：当n为0时，也就是i = j = 0，这时，说明不需要分配括号，直接返回字符串类型即可。

第二种：当i = 0，j > 0时，我们需要添加一个“）”类型，随即将j的值减一，然后进行递归判断。

第三种：当i > 0，j = 0时，我们需要添加一个“（”类型，随即将i的值减一，然后进行递归判断。

第四种：当i的值小于j的值时，我们也可以先添加“（”，令i的值减一后，递归（执行完之后进行回溯判断再次递归），再添加“）”，y - 1后再次进行递归操作。

第五种：当i的值大于等于j时，进行“（”的添加。

实例分析：输入：n =2。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
            vector<string> res;//最终存放的容器
            string s = "";//括号保存
            digui(res,n,n,s);//递归执行
            return res;
    }
    
    void digui(vector<string>&res,int i,int j,string s){
        if(i == 0 && j == 0){
            res.push_back(s);//直接存放
            return ;
        }
        if(i == 0 && j > 0){
            digui(res,i,j - 1,s + ")");//添加括号“）”，递归回溯
            return ;
        }
        if(j == 0 && i > 0){
            digui(res,i - 1,j,s + "(");//添加括号“（”，递归回溯
            return ;
        } 
        if(i < j){
            digui(res,i - 1,j,s + "(");//添加括号“（”，递归回溯
            digui(res,i,j - 1,s + ")");//添加括号“）”，递归回溯
            return ;
        }
        if(i >= j){
            digui(res,i - 1,j,s + "(");//添加括号“（”，递归回溯
            return ;
        }
    }
};

解法二：

思路分析：在上述解法当中，我们发现在括号没有完全匹配之前，右括号的使用数量应当小于左括号的使用数量。根据这一点直接使用递归完成括号的生成。

具体python代码为：

#
#
# @param n int整型
# @return string字符串一维数组
#
class Solution:
  def generateParenthesis(self, n: int):
      res = []#保存对象
      cur_str = ''#储存括号
      def dfs(cur_str, left, right):  #左括号或者右括号还可以使用的个数
          if left == 0 and right == 0:
              res.append(cur_str)
              return
          if right < left: #生成括号的过程中，右括号使用的个数是不能多于左括号使用的个数的 return if left > 0:
              dfs(cur_str + '(', left - 1, right)
          if right > 0:
              dfs(cur_str + ')', left, right - 1)
 
      dfs(cur_str, n, n)
      return res

编写python代码较为舒展，在计算的过程中应该始终坚持括号的优先原则，时间复杂度为O(N)，空间复杂度为O(N)。