leetcode 括号生成c++
程序员文章站
2022-07-14 17:42:03
...
题目:
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
分析:
- 括号成对出现
- 右括号不能比左括号先出现
解法:递归
class Solution {
public:
void backtrade(string str,vector<string>& res,int left,int right)
{
//str代表了构造的括号串
//res存放全部有效的括号串
//left代表未分配的左括号数量,right代表未分配的右括号数量
if(left>right) return ; //右括号比左括号先出现
if(left==0&&right==0)
res.push_back(str);
if(left>0) backtrade(str+'(',res,left-1,right);
if(right>0) backtrade(str+')',res,left,right-1);
}
vector<string> generateParenthesis(int n) {
vector<string> res;//存放结果
backtrade("",res,n,n);
return res;
}
};
上一篇: Android 控件位移动画
下一篇: Leetcode之 括号生成器