Leetcode題解 Python： Generate Parentheses

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

給一個數字 n ，要產生有 n 個左右成對「 ( ) 」的所有組合 。

說實在並不難，如果有想到左右成對的規則下，任何位置的左邊的 ( 數量一定得大於等於 )，不然會無法成對。

利用這特性，很快就可以寫出一個遞迴函數。

class Solution:
    def generateParenthesis(self, n):
        result = []
        def nextIdx(ln, rn, text):
            if ln == 0 and rn == 0:
                result.append(text)
            if ln - 1 >= 0:
                nextIdx(ln-1, rn, text+"(")
            if rn - 1 >= ln:
                nextIdx(ln, rn-1, text+")")
        nextIdx(n, n, "")
        return result

這是最直觀的寫法，速度也不錯。


換另外一種寫法 BackTracking。

class Solution:
    def generateParenthesis(self, n):
        """BackTracking"""
        result = []
        path = []
        def nextIdx(ln, rn):
            if ln == 0 and rn == 0:
                result.append("".join(path))
            if ln - 1 >= 0:
                path.append("(")
                nextIdx(ln-1, rn)
                del path[-1]
            if rn - 1 >= ln:
                path.append(")")
                nextIdx(ln, rn-1)
                del path[-1]

        nextIdx(n, n)
        return result

這種寫法就慢了一點，畢竟不會碰到下一步不合規則的判斷，如果真的盲選 ( 或 )寫入再判斷，應該只會更慢。

這題在子章節「unfold」，意思是不要寫得太精簡難懂。順著前進時，已經很習慣並不會覺得異樣，如果要倒退著，跟往前相比，就會覺得有點費力。

在前幾題有個求 1, 2, 3, ..., N個數有 K 種組合情形。那題使用尾呼叫會比較快速，這題也來嘗試使用那種模式回答。

class Solution:
    def generateParenthesis(self, n):
        """尾呼叫"""
        def nextIdx(ln, rn, text):
            res = []
            if ln == 0 and rn == 0:
                res.append(text)
                return res
            if ln - 1 >= 0:
                res.extend(nextIdx(ln-1, rn, text+"("))
            if rn - 1 >= ln:
                res.extend(nextIdx(ln, rn-1, text+")"))
            return res        
        return nextIdx(n, n, "")