题目描述
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
1
2
3
4
5
6
7
| [
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
|
参考
https://blog.csdn.net/yutianzuijin/article/details/13161721
解法很巧妙，看完立刻有想看编程之美书的冲动了！
《编程之美》的买票找零问题一样：2n个人排队买票，其中n个人持50元，n个人持100元。每张票50元，且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序，不至于使售票处找不开钱？可以把50块钱看成（，100块钱看成）。只有（始终大于等于）才可以找开钱。
通过买票找零问题我们可以知道，针对一个长度为2n的合法排列，第1到2n个位置都满足如下规则：左括号的个数大于等于右括号的个数。所以，我们就可以按照这个规则去打印括号：假设在位置k我们还剩余left个左括号和right个右括号，如果left>0，则我们可以直接打印左括号，而不违背规则。能否打印右括号，我们还必须验证left和right的值是否满足规则，如果left>=right，则我们不能打印右括号，因为打印会违背合法排列的规则，否则可以打印右括号。如果left和right均为零，则说明我们已经完成一个合法排列，可以将其打印出来。
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
30
31
32
33
34
| class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
rs_list = []
self.func_exe("", rs_list, n, n)
return rs_list
def func_exe(self, cur_str, rs_list, left, right):
"""
对任意一个合法匹配的括号串的任一位置，已经匹配的左括号的数量总是大于右括号的
即剩余匹配的右括号数大于左括号数
:param cur_str:当前括号串
:param rs_list: 所有的合法括号串集合
:param left: 剩余多少个左括号没填充
:param right: 剩余多少个左括号没填充
:return: None
"""
if left == 0 and right == 0:
rs_list.append(cur_str)
if left > 0:
self.func_exe(cur_str + "(", rs_list, left - 1, right)
if right > 0 and right > left:
self.func_exe(cur_str + ")", rs_list, left, right - 1)
if __name__ == '__main__':
s = Solution()
rs = s.generateParenthesis(3)
for item in rs:
print(item)
|
就3行代码，膜。。
