leetcode22 Generate Parentheses

 1 """
 2  Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
 3 For example, given n = 3, a solution set is:
 4 [
 5   "((()))",
 6   "(()())",
 7   "(())()",
 8   "()(())",
 9   "()()()"
10 ]
11 """
12 """
13 每次增加括号时需要判断之前字符串中左右括号的个数
14 判断增加‘(’或‘)’依据为，
15 #若当前字符串的长度等于2n则字符串存入列表中
16 若之前字符串中左括号个数小于n，则应增加左括号，
17 若之前字符串中右括号个数小于左括号，则应增加右括号
18 """
19 class Solution:
20     def generateParenthesis(self, n):
21         result = []
22         # 函数嵌套
23         def trackback(S="", left=0, right=0):
24             if len(S) == 2 * n:
25                 result.append(S)
26             if left < n:
27                 trackback(S + '(', left + 1, right)
28             if right < left:
29                 trackback(S + ')', left, right + 1)
30         trackback()
31         return result