欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 22. 括号生成 C++

程序员文章站 2022-07-14 17:41:27
...

Leetcode 22. 括号生成

题目

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

测试样例

输入:n = 3
输出:[
   "((()))",
   "(()())",
   "(())()",
   "()(())",
   "()()()"
 ]

题解

构造正确的n对括号可以通过回溯法构造,只需要保证任意位置前的右括号数目要小于等于左括号数码。因此在dfs中,我们用两个变量分别记录当前左括号的数目和当前右括号的数目。如果左括号数目小于n,那么我们就可以放置左括号;如果右括号数目小于左括号数目,我们就可以放置右括号。

代码

void dfs(int l,int r,int n,string &str,vector<string> &ans){
        if(r==n && l==n){
            ans.push_back(str);
        }
        if(l<n){		//当前可以放置左括号
            str.push_back('(');
            dfs(l+1,r,n,str,ans);
            str.pop_back();
        }
        if(l>r){		//当前可以放置右括号
            str.push_back(')');
            dfs(l,r+1,n,str,ans);
            str.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        if(n == 0)  return ans;
        string s;
        dfs(0,0,n,s,ans);
        return ans;
    }

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。