括号生成 （Python）

​​LeetCode链接​​

递归

首先考虑生成所有的情况，每一次都在之前的基础上加上一个左括号或者右括号，直到达到2n的长度为止

class Solution:
def generateParenthesis(self, n: int):
def generate(s):
if len(s) == 2 * n:
print(s)
else:
generate(s + '(')
generate(s + ')')
generate('')

在生成的途中加入有效性的判断：

• 左括号条件：left_count < n 就可以添加
• 右括号条件：有一个左括号才能添加一个有括号，所以条件为 right_count < left_count 时，才能添加

class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res_list = []
def generate(s, left_count, right_count):
# 终止条件
if left_count == n and right_count == n:
res_list.append(s)
else:
# 有效性判断
if left_count < n:
generate(s + '(', left_count + 1, right_count)
if right_count < left_count:
generate(s + ')', left_count, right_count + 1)
generate('', 0, 0)
return res_list