括号生成

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string>ans;
        string curArr;
        tryAdd(n*2,ans,curArr,0);
        return ans;
    }
    void tryAdd(int m,vector<string>&ans,string curArr,int depth){
        if(depth==m){
            if(isValid(curArr)){
                ans.push_back(curArr);
            }
            return;
        }
        curArr.push_back(‘(‘);
        tryAdd(m,ans,curArr,depth+1);
        curArr.pop_back();
        curArr.push_back(‘)‘);
        tryAdd(m,ans,curArr,depth+1);
    }
    bool isValid(string curArr){
        int balance=0;
        for(auto c:curArr){
            if(c==‘(‘)balance++;
            if(c==‘)‘)balance--;
            if(balance<0)return false;
        }
        if(balance==0)return true;
        else return false;
    }
};

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string>ans;
        string curArr;
        tryAdd(n*2,ans,curArr,0,0,0);
        return ans;
    }
    void tryAdd(int m,vector<string>&ans,string curArr,int depth,int cntLeft,int cntRight){
        if(depth==m){
            if(isValid(curArr)){
                ans.push_back(curArr);
            }
            return;
        }
        if(cntLeft<m/2){
            curArr.push_back(‘(‘);
            cntLeft++;
            tryAdd(m,ans,curArr,depth+1,cntLeft,cntRight);
            curArr.pop_back();
            cntLeft--;
        }
        if(cntRight<cntLeft){
            curArr.push_back(‘)‘);
            cntRight++;
            tryAdd(m,ans,curArr,depth+1,cntLeft,cntRight);
        }

    }
    bool isValid(string curArr){
        int balance=0;
        for(auto c:curArr){
            if(c==‘(‘)balance++;
            if(c==‘)‘)balance--;
            if(balance<0)return false;
        }
        if(balance==0)return true;
        else return false;
    }
};