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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
下一篇: 复习Python的Day4