问题
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
1
2
3
4
5
6
7
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Subscribe to see which companies asked this question.
解决思路和代码
递归一下就可以。代码用python实现的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
self.result = []
self.duang(0,0,n)
return (self.result)
'''
只要当前序列中的'('多于')'即合法
'''
def duang(self, left_n, right_n, max_n, base=''):
if left_n == max_n:
base += ')'*(max_n-right_n)
self.result.append(base)
return
if left_n > right_n:
self.duang(left_n+1, right_n, max_n, base+'(')
self.duang(left_n, right_n+1, max_n, base+')')
elif left_n == right_n:
self.duang(left_n+1, right_n, max_n, base+'(')
s = Solution()
s.generateParenthesis(3)