LeetCode解題之Generate Parentheses

原題

羅列出n組括號的所有合法的排列組合。

注意點：

例子：

輸入: n = 3
輸出: [‘((()))’, ‘(()())’, ‘(())()’, ‘()(())’, ‘()()()’]

解題思路

我們先來討論一下什麼樣的排列是不合法的，由於只有一種類型的括號，所以我們只要時刻保持字符串中的左括號不少於右括號即可。例如：字符串”)*“上來就右括號數目比左括號多，它就是不合法的，沒有左括號來與第一個右括號組合。在進行遞歸的時候注意優先添加左括號，在現有右括號少於左括號的情況下，可以添加右括號。遞歸的結束條件是所有的括號都已加入字符串中。

AC源碼

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        result = []
        self.generate(n, n, "", result)
        return result

    def generate(self, left, right, str, result):
        if left == 0 and right == 0:
            result.append(str)
            return
        if left > 0:
            self.generate(left - 1, right, str + "(", result)
        if right > left:
            self.generate(left, right - 1, str + ")", result)


if __name__ == "__main__":
    assert (Solution().generateParenthesis(3)) == ['((()))', '(()())', '(())()', '()(())', '()()()']

歡迎查看我的Github來獲得相關源碼。