給出 n 代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你寫出一個(gè)函數(shù)，使其能夠生成所有可能的并且有效的括號(hào)組合。
例如鸽嫂，給出 n = __3纵装，生成結(jié)果為：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Image.png
code:
# 使用遞規(guī)來(lái)求解，當(dāng)右括號(hào)多于左括號(hào)的時(shí)候溪胶，就不符合條件了進(jìn)行剪枝
class Solution:
def generateParenthesis(self, n):
if n == 0:
return []
result = []
self.helper(n, n, '', result)
return result
def helper(self, l, r, item, result):
# 當(dāng)剩余左括號(hào)大于右括號(hào)搂擦，說明右括號(hào)大于左括號(hào)，就不符合條件了
if l > r:
return
if l == r == 0:
result.append(item)
# 左括號(hào)大于0哗脖，就增加一個(gè)左括號(hào)
if l > 0:
self.helper(l - 1, r, item + '(', result)
# 右括號(hào)大于0瀑踢，就增加一個(gè)右括號(hào)
if r > 0:
self.helper(l, r - 1, item + ')', result)
