leetcode-22：括号生成

题目

题目连接

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

示例 1：

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

示例 2：

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

解题

如果直接暴力回溯，让’('和‘)'自由组合，然后判断括号有效性，这样做，复杂度会比较高。
因此可以在直接通过一些判断条件，使得生成的括号是有效的。

方法一：回溯

通过open ，close来计数 开闭括号数量，保证close<open才会加入闭括号，以此来保证生成的括号的有效性。

class Solution {
    
public:
    string path;
    vector<string> res;
    void dfs(int open,int close,int n){
    
        if(path.size()==n*2){
    
            res.push_back(path);
            return;
        }
        if(open<n){
    
            path.push_back('(');
            dfs(open+1,close,n);
            path.pop_back();
        }
        if(close<open){
    
            path.push_back(')');
            dfs(open,close+1,n);
            path.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
    
        dfs(0,0,n);
        return res;
    }
};