Leetcode 22. 括号生成 C++

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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。