首页 > itarticle > [leetcode]递归解决q22问题

[leetcode]递归解决q22问题

admin 11月 12, 2020 0

问题

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

For example, given n = 3, a solution set is:

[
 "((()))",
 "(()())",
 "(())()",
 "()(())",
 "()()()"
]

Subscribe to see which companies asked this question.

解决思路和代码

递归一下就可以。代码用python实现的：

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

    '''
    只要当前序列中的'('多于')'即合法
    '''
    def duang(self, left_n, right_n, max_n, base=''):
        if left_n == max_n:
            base += ')'*(max_n-right_n)
            self.result.append(base)
            return

        if left_n > right_n:
            self.duang(left_n+1, right_n, max_n, base+'(')
            self.duang(left_n, right_n+1, max_n, base+')')

        elif left_n == right_n:
            self.duang(left_n+1, right_n, max_n, base+'(')

s = Solution()
s.generateParenthesis(3)