題目:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

給定一數n,回傳所有n個括號的排列可能(括號需有對應,像")("就不行)

我發現只要在n-1個括號的所有排列可能裡所有的"("後加上"()"
再特別考慮"()()()..."這種可能,就考慮到了n個括號的所有排列可能
ex:n=2,所有可能會是["()()"和"(())"]
"()()"=>"(())()","()(())"
"(())"=>"(()())","((()))"
特別考慮=>"()()()"
而n=3的所有可能即為["((()))","(()())","(())()","()(())","()()()"]

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans=["()"]
        
        for i in range(n-1):
            temp=[]
            temp.append(ans[0]+"()")
            for j in range(len(ans)):
                for k in range(len(ans[j])):
                    if ans[j][k]=="(":
                        t=ans[j][0:k+1]+"()"+ans[j][k+1:len(ans[j])]
                        if t not in temp:
                            temp.append(t)
            ans=temp
                 
        return ans

以初始陣列["()"]出發推斷出後續可能
第一項固定放"()()()...."類型的組合
所以先將紀錄前一次所有可能的陣列(ans)的第一項後加上"()"
放入紀錄此次所有可能的陣列(temp)

接著將ans內裡所有元素一一操作
在"("後加上"()"放入temp內
但為防止重複紀錄,先確認該可能不在temp內後再加入
完全執行完後將ans變為temp,進入下一次迴圈
迴圈執行結束後回傳ans
最後執行時間114ms(faster than 5.07%)

然而我的解法效率低落,於是我開始瀏覽討論區
看到了下面這個解法

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans=[]
        temp=[]
        
        def x(opencnt,closecnt):
            if opencnt==closecnt==n:
                ans.append("".join(temp))
                return
            
            if opencnt<n:
                temp.append("(")
                x(opencnt+1,closecnt)
                temp.pop()
                
            if closecnt<opencnt:
                temp.append(")")
                x(opencnt,closecnt+1)
                temp.pop()
        
        x(0,0)
        return ans

是個遞迴解,紀錄目前使用的"("和")"個數來繼續推測接下來的可能

我們最多可以使用n個"("和n個")"來排列可能
而排列過程中絕不能使")"的使用次數(closecnt)超過"("的使用次數(opencnt)
否則會造成不合理的組合出現(如:")(","())(()")

所以當我們決定下一個括號要排什麼時
只要opencnt< n我們下一項就可以選擇放"("
而當closecnt< opencnt我們又多了")"可以選擇

函式(x)需要的輸入資料即opencnt和closecnt
當前的排列順序都記錄在temp
當opencnt==closecnt==n時,代表這時temp內裝的是其中一種可能
將其透過join變為字串後放入ans,return

而當opencnt< n,我們選擇放"("至temp內
往下執行x(opencnt+1,closecnt)繼續探索此排列之後的可能
執行結束後將剛填入的"("pop掉(此排列之後的可能已全部被探索且記錄)

而又當closecnt< opencnt,我們選擇放")"至temp內
往下執行x(opencnt,closecnt+1)繼續探索此排列之後的可能
執行結束後將剛填入的")"pop掉(此排列之後的可能已全部被探索且記錄)

執行x(0,0),結束後ans內已有所有n個括號的排列可能
回傳ans
最後執行時間34ms(faster than 95.21%)

那我們下題見