LeetCode 22. 括号生成(C++)
程序员文章站
2022-07-14 17:50:00
...
题目描述
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
思路
这道题采用递归的方法求解,难点在于怎样构造递归函数。建立left和right两个变量表示剩余的括号数,因此递归结束的条件就是left>right时不满足条件直接返回,括号用完时(left=right=0)加入到返回vector中。值得注意的是使用C++是想要得到返回数组必须采用**&(深拷贝,即引用)**的方式作为函数参数。
代码
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> re;
generateAll("",re,n,n);
return re;
}
void generateAll(string subs,vector<string>& re,int left,int right) //&引用
{
if(left>right) return ;
if(left==0 && right==0)
{
re.push_back(subs);
return ;
}
if(left>0) generateAll(subs+"(",re,left-1,right);
if(right>0) generateAll(subs+")",re,left,right-1);
}
};