当前位置：网站首页>22. Bracket generation

22. Bracket generation

2022-04-23 12:51:00 【anieoo】

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();
    }
};

 

版权声明
本文为[anieoo]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204231248410369.html

边栏推荐

猜你喜欢

随机推荐