当前位置：网站首页>22. 括号生成

22. 括号生成

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

原题链接：22. 括号生成

 

solution：dfs+回溯

可以观察到一个性质,左括号数量永远大于等于右括号数量

然后就是一道简的dfs问题了

class Solution {
public:
    vector<string> res; //定义返回值
    vector<string> generateParenthesis(int n) {
        string str = "";    //保存单个有效括号字符串
        dfs(0,0,n,str); //dfs遍历
        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(); //回溯
        str.push_back(')');
        dfs(l,r + 1,n,str);
        str.pop_back();
    }
};

 

版权声明
本文为[anieoo]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_42174306/article/details/124360629

边栏推荐

猜你喜欢

随机推荐