題目
給出 n 代表生成括號的對數(shù)梅桩，請你寫出一個(gè)函數(shù)讯私，使其能夠生成所有可能的并且有效的括號組合缀皱。
例如，給出 n = 3晒奕，生成結(jié)果為：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解答
我們可以采用暴力求解法闻书，生成所有可能的組合，再用【20. 有效的括號】中的方法一一判斷是否合法脑慧，不過這樣的時(shí)間和空間復(fù)雜度太高魄眉，這里我們采用回溯法，在生成括號時(shí)就按照規(guī)則生成闷袒。
定義函數(shù)backtrack坑律，函數(shù)輸入一個(gè)當(dāng)前字符串和當(dāng)前左右括號各自的數(shù)目，函數(shù)執(zhí)行的操作是嘗試進(jìn)行三個(gè)判斷：
- 如果當(dāng)前總數(shù)目已經(jīng)達(dá)到要求，則直接添加到結(jié)果并跳出函數(shù)晃择；
- 如果當(dāng)前左括號個(gè)數(shù)合法（小于n）冀值，可以再添加一個(gè)左括號；
- 如果當(dāng)前右括號個(gè)數(shù)合法（小于左括號個(gè)數(shù)）宫屠，可以再添加一個(gè)右括號列疗。
class Solution(object):
def generateParenthesis(self, n):
ans = []
def backtrack(S = '', left = 0, right = 0):
if len(S) == 2 * n:
ans.append(S)
return
if left < n:
backtrack(S+'(', left+1, right)
if right < left:
backtrack(S+')', left, right+1)
backtrack()
return ans
如有疑問或建議，歡迎評論區(qū)留言~
