Leetcode-22: bracket generation

subject

Topic linking

Numbers n Represents the logarithm of the generated bracket , Please design a function , Used to be able to generate all possible and Effective Bracket combination .

Example 1：

 Input ：n = 3
 Output ：["((()))","(()())","(())()","()(())","()()()"]

Example 2：

 Input ：n = 1
 Output ：["()"]

Problem solving

If direct violence is traced , Give Way ’(' and ‘)' Free combination , Then judge the validity of brackets , To do so , The complexity will be relatively high .
Therefore, we can directly pass some judgment conditions , Make the generated parentheses valid .

Method 1 ： to flash back

adopt open ,close To count Number of opening and closing brackets , Guarantee close<open Will add closed parentheses , To ensure the validity of the generated parentheses .

class Solution {
    
public:
    string path;
    vector<string> res;
    void dfs(int open,int close,int n){
    
        if(path.size()==n*2){
    
            res.push_back(path);
            return;
        }
        if(open<n){
    
            path.push_back('(');
            dfs(open+1,close,n);
            path.pop_back();
        }
        if(close<open){
    
            path.push_back(')');
            dfs(open,close+1,n);
            path.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
    
        dfs(0,0,n);
        return res;
    }
};