题目内容

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

示例

示例 1：

输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

示例 2：

输入：n = 1
输出：[“()”]

提示

1 <= n <= 8

题解

这个题比较特殊，一般的求解思路在这里都会比较麻烦。这里破题的点在于思考括号生成的条件，这里给出来，大家以后记住就好。推论如下：

在假设括号类型相同的情况下有：

1、任意字符串前缀，左括号数量一定大于等于右括号数量

2、从整体来看，左右括号数量一定相等

本题需要根据以上信息，进行求解。

因为是一种搜索生成有效的括号的实例，所以我们可以采用最常见的深度优先遍历搜索算法，以递归的实现方式来求解题目。

在实现dfs函数中，需要传入的变量有：题目中给出的括号对数n、当前搜索中左括号的数量lc、当前搜索中右括号的数量rc，以及当前搜索的括号字符串结果seq。

具体，请看代码实现以及注释即可。

代码

class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        /*
            在什么情况下n个左括号和n个右括号构成的序列是合法的，存在一个推论,如下。（这里要求括号类型要相同）
                1、任意前缀中，左括号数量大于等于右括号数量
                2、左右括号数量相等
            
            在本题中，根据以上信息，利用深度优先算法，使用递归的思想来求解。
        */
        dfs(n,0,0,"");
        return res;
    }

    //n代表括号对数，lc代表目前seq中左括号的数量，rc代表目前seq中右括号的数量，seq代表当前的括号字符串结果。
    void dfs(int n, int lc, int rc, string seq){
        //当左括号和右括号的数量均为n时，代表结束，产生的结果应放入结果中
        if(lc == n && rc == n) res.push_back(seq);
        else{
            //当左括号没有达到n的数量时，就可以增加
            if(lc < n) dfs(n,lc + 1, rc, seq+'(');
            //当右括号没有达到n的数量时，左括号的数量必须严格大于右括号的数量的情况下才可以添加右括号，因为如果加上相等的条件，可能会造成前缀中，右括号的数量大于左括号的数量，条件会不满足！
            if(rc < n && lc > rc) dfs(n, lc, rc + 1, seq + ')');
        }
    }
};