今天是紀錄LeetCode解題的第二十二天

第二十二題題目：Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

給定ｎ對括號，寫定一個函數來產生所有格式正確的括號組合

解題思路

這題我們用回溯法，如果左括號數量小於n，那麼我們就增加左括號，然後呼叫自己進到下一次函式裡，同理，當右括號數量小於左括號，也是一樣呼叫自己，每次進到函式都判斷目前的括號數量是否等於n*2，如果是的話，則把此次結果儲存起來，並且回溯繼續找下一個組合

程式碼

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

呼叫樹對照圖(n=2)

執行順序