22. 括号生成

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

示例：

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

class Solution {
vector<string> ret;
int z = 0;
public:
    bool panduan(string ss){
        int n = ss.length();
        int booll =0;
        for(int i = 0;i<n;i++){
            if(ss[i]=='('){
                booll++;
            }
            else {
                booll--;
            }
            if(booll<0){
                return false;
            }
        }
        if(booll==0){
            return true;
        }
        return false;
    } 
    void dfs(int n,string tem){
        if(tem.length()>=n*2){
            if(panduan(tem)){
                ret.push_back(tem);
            }
            return ;
        }
        dfs(n,tem+"(");
        dfs(n,tem+")");
    }
    vector<string> generateParenthesis(int n) {
        dfs(n,"(");
        return ret;
    }
};

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        func(res, "", n, n);
        return res;
    }

    void func(vector<string> &res, string str, int l, int r){
        if(l == 0 && r == 0){
            res.push_back(str);
            return;
        }
        if(l > 0){
            func(res, str + '(', l-1, r);
        }
        if(r > 0 && r > l){
            func(res, str + ')', l, r-1);
        }
        return;
    }
};

作者：chengm15
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/zui-ji-ben-de-dfs-by-chengm15/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。