题解 | 括号生成

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> ans;
    string res = "";
    vector<char> vechar={'(',')'};
    bool IsValid(string &res){
        stack<char> sta;
        if(res.size()%2!=0) return false;
        if(res.empty()) return true;
        if(res.at(0)!='(' || res.back()!=')') return false;
        for(const char & ch:res){
            if(ch=='(') sta.push(ch);
            if(ch==')') {
                if(sta.empty()) return false;
                else if(sta.top()=='(') {sta.pop();} 
                else sta.push(ch);
            }
        }
        if(sta.empty()) return true;
        else return false;
    }

    void generate(int n){
        if(res.size()>=2*n) {
            if(IsValid(res)) {ans.push_back(res);}
            return;
        }
        for(const char & ch:vechar){
            res  +=ch;
            // cout<<res<<endl;
            generate(n);
            res.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        // write code here
        generate(n);
        return ans;
    }
};