題目

給出 n 代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你寫出一個(gè)函數(shù)，使其能夠生成所有可能的并且有效的括號(hào)組合。

例如，給出 n = 3，生成結(jié)果為：

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

解答

我們可以采用暴力求解法，生成所有可能的組合，再用【20. 有效的括號(hào)】中的方法一一判斷是否合法，不過(guò)這樣的時(shí)間和空間復(fù)雜度太高，這里我們采用回溯法，在生成括號(hào)時(shí)就按照規(guī)則生成。

定義函數(shù)backtrack，函數(shù)輸入一個(gè)當(dāng)前字符串和當(dāng)前左右括號(hào)各自的數(shù)目，函數(shù)執(zhí)行的操作是嘗試進(jìn)行三個(gè)判斷：

1. 如果當(dāng)前總數(shù)目已經(jīng)達(dá)到要求，則直接添加到結(jié)果并跳出函數(shù)；
2. 如果當(dāng)前左括號(hào)個(gè)數(shù)合法（小于n），可以再添加一個(gè)左括號(hào)；
3. 如果當(dāng)前右括號(hào)個(gè)數(shù)合法（小于左括號(hào)個(gè)數(shù)），可以再添加一個(gè)右括號(hào)。

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

如有疑問(wèn)或建議，歡迎評(píng)論區(qū)留言~