leetcode-22. 括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

思路

1）回溯

2）结束条件：构建的字符串长度==2*n

3）注意两点回溯的判断：if left<n；if right<left

class Solution(object):
    def __init__(self):
        self.res = []

    def backtrack(self,s,n,left,right):
        if len(s) == 2*n:
            self.res.append("".join(s))
            return
        if left<n:
            s.append('(')
            self.backtrack(s,n,left+1,right)
            s.pop()
        if right<left:
            s.append(')')
            self.backtrack(s,n,left,right+1)
            s.pop()

    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        s = []
        left = right = 0
        self.backtrack(s,n,left,right)
        return self.res

if __name__ == '__main__':
    s=Solution()
    n = 3
    print(s.generateParenthesis(n))