题解 | #括号生成#

class Solution {
private:
    string path = "";
    vector<string> res;
    vector<char> src = {'(', ')'};
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> generateParenthesis(int n) {
        // write code here
        dfs(2*n);
        return res;
    }
    
    void dfs(int n){
        if(n <= 0){
            if(check(path)){
                res.push_back(path);
            }
            return;
        }
        
        for(int i=0; i<src.size(); i++){
            path.push_back(src[i]);
            dfs(n-1);
            path.pop_back();
        }
        
    }
    
    bool check(string s){
        if(s.length() % 2 != 0){
            return false;
        }
        
        stack<char> st;
        int i = 0;
        while(i < s.length()){
            if(s[i] == '('){
                st.push(s[i]);
            }
            else{
                if(st.empty()){
                    return false;
                }
                st.pop();
            }
            i++;
        }
        
        if(!st.empty()){
            return false;
        }
        
        return true;
    }
    
};