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

动态规划
代码如下：

class Solution:
    def generateParenthesis(self, n):
        def gen(rightSymbol, leftSymbol, path, res):
            if leftSymbol < rightSymbol or rightSymbol > n or leftSymbol > n:  # 左括号小于右括号，右括号大于n，左括号大于n都不合法
                return
            if leftSymbol == rightSymbol == n:
                res.append(path)
            path += "("
            gen(rightSymbol, leftSymbol + 1, path, res)
            path = path[:-1]
            path += ")"
            gen(rightSymbol + 1, leftSymbol, path, res)
            path = path[:-1]
            return res

        return gen(0, 0, "", [])