【leetcode刷题】T65-括号生成
【题目】
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
【思路】
什么是有效的括号？可以参考【T19-有效的括号】。
可以这样理解：从左往右对元素进行计数，左括号的个数始终大于等于右括号的个数。
有一个很自然的想法，使用递归，使用变量left和right分别存储左括号和右括号剩余可用个数，当left>0，继续递归（left-1）；当right>left，继续递归（right-1）；当left和right都为0，满足条件，加入结果。
【代码】
python版本
class Solution(object):
def loop(self, sub, res, left, right):
if left == and right == :
res.append(sub)
return
# 还有左括号
if left > :
self.loop(sub+'(', res, left-1, right)
# 右括号数大于左括号数
if right > left:
self.loop(sub+')', res, left, right-1)
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
res = []
self.loop('', res, n, n)
return res
C++版本
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
loop("", res, n, n);
return res;
}
void loop(string s, vector<string>& res, int left, int right){
if(left == && right == ){
res.push_back(s);
return ;
}
// 还有左括号
if(left > )
loop(s + "(", res, left-1, right);
// 右括号数大于左括号数
if(right > left)
loop(s + ")", res, left, right-1);
}
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-05-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
