# 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:
#
# [
# "((()))",
# "(()())",
# "(())()",
# "()(())",
# "()()()"
# ]
l_num = 剩余的 左括号数
r_num = 剩余的 右括号数
只需要保证 l_num <= r_num ,当前的组合就一定是有效的。
class Solution():
def generateParenthesis(self, n):
res = []
self.generate(res, '', n, n)
return res
def generate(self, res, cur, l_num, r_num):
if l_num <= r_num:
if r_num == 0:
res.append(cur)
return
if l_num > 0:
self.generate(res, cur+'(', l_num-1, r_num)
if r_num > 0:
self.generate(res, cur+')', l_num, r_num-1)
if __name__ == "__main__":
assert Solution().generateParenthesis(3) == ['((()))', '(()())', '(())()', '()(())', '()()()']