Generate Parentheses (Python)

kitt posted @ 2014年2月10日 17:16 in LeetCode , 3144 阅读

递归方法，确保在每一步右括号数 <= 左括号数 <= n即可。

class Solution:
    # @param an integer
    # @return a list of string
    def gen(self, s, leftParenNum, rightParenNum):
        if leftParenNum == rightParenNum == Solution.n:
            Solution.res.append(s)
            return
        if leftParenNum < Solution.n:
           self.gen(s + '(', leftParenNum + 1, rightParenNum)
        if rightParenNum < leftParenNum <= Solution.n:
           self.gen(s + ')', leftParenNum, rightParenNum + 1)
        return

    def generateParenthesis(self, n):
        Solution.n = n
        Solution.res = []
        self.gen('', 0, 0)
        return Solution.res