LeetCode 22 [Generate Parentheses]

look_w

原题

    给定 n 对括号，请写一个函数以将其生成新的括号组合，并返回所有组合结果。

样例
给定 n = 3, 可生成的组合如下:
"((()))", "(()())", "(())()", "()(())", "()()()"
解题思路

    求所有的组合，递归， backtracking
    left，right分别代表左括号和右括号还剩几个 - 规则就是：任何时候剩余的右括号都要大于等于左括号
    当left和right都等于零的时候，向result中添加一个可行解

完整代码

    class Solution(object):
        def generateParenthesis(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
            res = []
            if n < 1:
                return res
            self.helper(n, n, "", res)
            return res
            
        def helper(self, left, right, path, res):
            if left > right:
                return
            if left == 0 and right == 0:
                res.append(path)
            if left > 0:
                self.helper(left - 1, right, path + "(", res)
            if right > 0:
                self.helper(left, right - 1, path + ")", res)