Leetcode第二十二题(括号生成)

题目描述:

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

class Solution {
    vector<string> ans;
    string cur;
public:
    vector<string> generateParenthesis(int n) {
        dfs(0,0,n);
        return ans;
    }
    void dfs(int lc,int rc,int n){
        //lc 左括号数量  rc 右括号数量  n 括号对数   
        if(lc == n && rc == n){
            ans.push_back(cur);
            return;
        }
        if(lc < n) {
            cur.push_back('(');
            dfs(lc + 1, rc ,n);
            cur.pop_back();
        }
        //只有当左括号比右括号多的时候插入右括号生成的括号组合才是有效的
        if(rc < n && lc > rc) {
            cur.push_back(')');
            dfs(lc, rc + 1 ,n);
            cur.pop_back();
        }
    }
};

class Solution {
    vector<string> ans;
public:
    vector<string> generateParenthesis(int n) {
        dfs(0,0,n,"");
        return ans;
    }
    void dfs(int lc,int rc,int n,string seq){
        //lc 左括号数量  rc 右括号数量  n 括号对数   
        if(lc == n && rc == n){
            ans.push_back(seq);
            return;
        }
        if(lc < n) dfs(lc + 1,rc,n,seq + "(");
        //只有当左括号比右括号多的时候插入右括号生成的括号组合才是有效的
        if(rc < n && lc > rc) dfs(lc,rc + 1,n,seq + ")");
    }
};