1、题目
输入数字n，输出n对括号的可能组合。
"""
示例1：
输入：3
输出:()()(),()(()),(())(),((()))
"""
2、代码

        def generateParenthesis(n):
            """动态规划，状态转移
                (1)对于长度为i的括号组合，我们可以通过在长度为j的括号组合中插入新的括号来生成。
                (2)遍历长度为1到n的所有括号组合，然后在每个长度为i的括号组合中，遍历长度为j的括号组合，并在每个位置插入新的括号。
                (3)插入方法是:遍历以前的所有组合(0,i-1)，组合位置j(j为0到i-1)与 i-j-1 状态(因为这两个位置加和为i-1，再加上一个括号，即为i个括号)。
                (4)将新生成的括号组合添加到长度为i的括号组合列表中。
            返回结果：返回长度为n的所有合法的括号组合，即为 dp[n]。
            """
            if n == 0:  # n为0，则直接返回一个包含空字符串的列表，表示长度为0的括号组合只有一个空字符串。
                return ['']
            dp = [[] for _ in range(n + 1)]  # 创建一个二维数组 dp，dp[i] 表示长度为i的所有合法的括号组合
            dp[0].append('')  # 初始化长度为0的括号组合为一个包含空字符串的列表，表示长度为0的括号组合只有一个空字符串
            for i in range(1, n + 1):  # 遍历长度为1到n的所有括号组合
                for j in range(i):  # 在生成长度为i的括号组合时，遍历长度为j的括号组合，其中j的取值范围为0到i-1
                    for x in dp[j]:  # 遍历第j个位置的括号
                        for y in dp[i - j - 1]:  # 对于长度为i-j-1的括号组合中的每个字符串y
                            dp[i].append('(' + x + ')' + y)  # 插入左右括号，并与第i-j-1位置的括号组合
                print(f"i:{i},dp[i]:{dp[i]}")
            return dp[n]