题目
给定数字n，输出合法的括号组合，结果由n个括号组成
例如：输入为2
输出结果为： “(())”,”()()”
分析
该题目实际上即为考察二叉树，即左分支用于添加”(“,右分支用于添加”)”
python代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class (object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
res = self.dfs([], "", n, n)
return res
def dfs(self, res, tmp, left, right):
if(0==left and 0==right):
res.append(tmp)
return
elif left > 0:
self.dfs(res, tmp + "(", left-1, right)
if right > left:
self.dfs(res, tmp + ")", left, right-1)
return res
|
C++代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
vector<string> generateParenthesis(int n) {
if (n == 0) return vector<string>();
vector<string > ret;
dfs(ret, "", n, n);
return ret;
}
void dfs(vector<string> &ret, string tmp, int left, int right)
{
if (0 == left && 0 == right)
{
ret.push_back(tmp);
return;
}
else if (left > 0)
dfs(ret, tmp + '(', left - 1, right);
if (left < right)
dfs(ret, tmp + ')', left, right - 1);
}
};
|
近期评论