括号生成

三道括号题目

括号生成

22.括号生成

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

有关括号问题，只要记住以下性质，思路就很容易想出来：

1、一个“合法”括号组合的左括号数量一定等于右括号数量

2、对于一个“合法”的括号字符串组合s，必然对于任何0<=i<s.size()都有：子串s[0…i]中左括号的数量都大于或等于右括号的数量。（因为是从左到右算的）

思路：算法输入一个整数n，让你计算n对括号能组成几种合法的括号组合，可以改写程如下问题：

现在有2n个位置，每个位置可以放置字符(或者)，组成的所有括号组合中，有多少个是合法的？

class Solution {
public:
    vector<string> res;
    string temp;
    vector<string> generateParenthesis(int n) {
        if(n==0) return {};
        //可用的左括号和右括号数量初始为 n
        dfs(n, n);
        return res;
    }
    void dfs(int left, int right){ //可用的左括号为left个，可用的右括号为right个
        //不合法，结束
        if(left<0 || right<0) return;
        //若剩下的左括号多，不合法
        if(right<left) return;

        //当所有括号都恰好用完时，得到一个合法的组合
        if(left==0 && right==0){
            res.push_back(temp);
            return;
        }
        //尝试添加一个左括号
        temp.push_back('(');
        dfs(left-1, right);
        temp.pop_back();

        //尝试添加一个右括号
        temp.push_back(')');
        dfs(left, right-1);
        temp.pop_back();
    }
};