【从0到1冲刺蓝桥杯国赛】每日一练——括号生成

 括号生成https://leetcode-cn.com/problems/generate-parentheses/

这道题最好的做法是DFS，这里我直接讲DFS的做法。
首先我们需要知道一个结论，一个合法的括号序列需要满足两个条件：

左右括号数量相等任意前缀左中括号数量>=右括号数量（也就是说每一个右括号总能找到相对应的左括号）

class Solution {
public:
    vector res; //记录答案 
    vector generateParenthesis(int n) {
        dfs(n , 0 , 0, "");
        return res;
    }
    void dfs(int n ,int lc, int rc ,string str)
    {
        if( lc == n && rc == n) res.push_back(str);    //递归边界
        else
        {
            if(lc < n) dfs(n, lc + 1, rc, str + "(");            //拼接左括号
            if(rc < n && lc > rc) dfs(n, lc, rc + 1, str + ")"); //拼接右括号
        }
    }
};

网友思路写得很好：

网友思路（DFS）https://leetcode-cn.com/problems/generate-parentheses/solution/shen-du-you-xian-bian-li-zui-jian-jie-yi-ypti/