22. Bracket generation

Original link ：22. Bracket generation

solution：dfs+ to flash back

A property can be observed , The number of left parentheses is always greater than or equal to the number of right parentheses

Then there's a simple one dfs Problem.

class Solution {
public:
    vector<string> res; // Define the return value 
    vector<string> generateParenthesis(int n) {
        string str = "";    // Save a single valid parenthesis string 
        dfs(0,0,n,str); //dfs Traverse 
        return res;
    }

    void dfs(int l,int r,int n,string &str) {
        if(l > n || r > n || r > l) return;
        if(l == n && r== n){
            res.push_back(str);
            return;
        }
        str.push_back('(');
        dfs(l + 1,r,n,str);
        str.pop_back(); // to flash back 
        str.push_back(')');
        dfs(l,r + 1,n,str);
        str.pop_back();
    }
};