题解 | #括号生成#

题目主要信息：

• 求n对括号的全部合法组合，左右括号之间任意组合，只要合法就行
• 需要输出所有的结果

举一反三：

学习完本题的思路你可以解决如下题目：

BM55. 没有重复项数字的全排列

BM56. 有重复项数字的全排列

BM58. 字符串的排列

方法：递归（推荐使用）

知识点：递归与回溯

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。

思路：

相当于一共$nn$个左括号和$nn$个右括号，可以给我们使用，我们需要依次组装这些括号。每当我们使用一个左括号之后，就剩下$n-1n-1$个左括号和$nn$个右括号给我们使用，结果拼在使用的左括号之后就行了，因此后者就是一个子问题，可以使用递归：

• 终止条件： 左右括号都使用了n个，将结果加入数组。
• 返回值： 每一级向上一级返回后续组装后的字符串，即子问题中搭配出来的括号序列。
• 本级任务： 每一级就是保证左括号还有剩余的情况下，使用一次左括号进入子问题，或者右括号还有剩余且右括号使用次数少于左括号的情况下使用一次右括号进入子问题。

但是这样递归不能保证括号一定合法，我们需要保证左括号出现的次数比右括号多时我们再使用右括号就一定能保证括号合法了，因此每次需要检查左括号和右括号的使用次数。

//使用一次左括号
if(left < n){
    recursion(left + 1, right, temp + "(", res, n);
}
//使用右括号个数必须少于左括号
if(right < n && left > right){ 
    recursion(left, right + 1, temp + ")", res, n);
}

具体做法：

• step 1：将空串与左右括号各自使用了0个送入递归。
• step 2：若是左右括号都使用了$nn$个，此时就是一种结果。
• step 3：若是左括号数没有到达$nn$个，可以考虑增加左括号，或者右括号数没有到达$nn$个且左括号的使用次数多于右括号就可以增加右括号。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public void recursion(int left, int right, String temp, ArrayList<String> res, int n){
        //左右括号都用完了，就加入结果
        if(left == n && right == n){ 
            res.add(temp);
            return;
        }
        //使用一次左括号
        if(left < n){
            recursion(left + 1, right, temp + "(", res, n);
        }
        //使用右括号个数必须少于左括号
        if(right < n && left > right){ 
            recursion(left, right + 1, temp + ")", res, n);
        }
    }
    public ArrayList<String> generateParenthesis (int n) {
        //记录结果
        ArrayList<String> res = new ArrayList<String>(); 
        //递归
        recursion(0, 0, "", res, n); 
        return res;
    }
}

C++实现代码：

class Solution {
public:
    void recursion(int left, int right, string temp, vector<string> &res, int n){
        //左右括号都用完了，就加入结果
        if(left == n && right == n){ 
            res.push_back(temp);
            return;
        }
        //使用一次左括号
        if(left < n) 
            recursion(left + 1, right, temp + "(", res, n);
        //使用右括号个数必须少于左括号
        if(right < n && left > right) 
            recursion(left, right + 1, temp + ")", res, n);
    }
    
    vector<string> generateParenthesis(int n) {
        //记录结果
        vector<string> res; 
        //记录每次组装的字符串
        string temp; 
        //递归
        recursion(0, 0, temp, res, n); 
        return res;
    }
};

Python实现代码：

class Solution:
    def recursion(self, left:int, right:int, temp:str, res:List[str], n:int):
        #左右括号都用完了，就加入结果
        if left == n and right == n: 
            res.append(temp)
            return
        #使用一次左括号
        if left < n: 
            self.recursion(left + 1, right, temp + "(", res, n)
        #使用右括号个数必须少于左括号
        if right < n and left > right: 
            self.recursion(left, right + 1, temp + ")", res, n)
            
    def generateParenthesis(self , n: int) -> List[str]:
        #记录结果
        res = list()
        #记录每次组装的字符串 
        temp = str() 
        #递归
        self.recursion(0, 0, temp, res, n) 
        return res

复杂度分析：

• 时间复杂度：$O(\frac{4^n}{\sqrt{n}})O(\backslash frac\{4^n\}\{\backslash sqrt\{n\}\})$，复杂度取决于有多少个合法括号组合，这是第n个卡特兰数，由$\frac{4^n}{n\sqrt{n}}\backslash frac\{4^n\}\{n\backslash sqrt\{n\}\}$渐近界定的
• 空间复杂度：$O(n)O(n)$，递归栈最大空间，其中res数组是返回时必须要的，不算额外空间