1 題目

數字 n 代表生成括號的對數，請你設計一個函數，用於能夠生成所有可能的並且 有效的 括號組合。

示例 1：

輸入：n = 3
輸出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：

輸入：n = 1
輸出：[“()”]

2 解析

（1）方法一：暴力求解
為了生成所有序列，我們可以使用遞歸。長度為 nn 的序列就是在長度為 n−1 的序列前加一個 (’ 或 ‘)’。

為了檢查序列是否有效，我們遍歷這個序列，並使用一個變量balance 表示左括號的數量減去右括號的數量。如果在遍歷過程中 balance 的值小於零，或者結束時balance 的值不為零，那麼該序列就是無效的，否則它是有效的。
（2）方法二：回溯方法

如果左括號數量不大於 n，我們可以放一個左括號。如果右括號數量小於左括號的數量，我們可以放一個右括號。

3 Python實現

（1）方法一

class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def generate(A):
if len(A) == 2*n:
if valid(A):
ans.append(''.join(A))
else:
A.append('(')
generate(A)
A.pop()
A.append(')')
generate(A)
A.pop()
def valid(A):
bal = 0
for c in A:
if c == '(':
bal += 1
else:
bal -= 1
if bal < 0:
return False
return bal == 0
ans = []
generate([])
return ans

（2）方法二

class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def backtrack(A,left,right):
if len(A)==2*n:
ans.append(''.join(A))
return
if left <n:
A.append('(')
backtrack(A,left+1,right)
A.pop()
if right<left:
A.append(')')
backtrack(A, left, right+1)
A.pop()
ans = []
backtrack([],0,0)
return ans