数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
方法一： 深度优先遍历 题解
执行用时：40 ms, 在所有 Python3 提交中击败了83.34%的用户 内存消耗：13.9 MB, 在所有 Python3 提交中击败了6.06%的用户 from typing import List class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] cur_str = '' def dfs(cur_str, left, right): """ :param cur_str: 从根结点到叶子结点的路径字符串 :param left: 左括号还可以使用的个数 :param right: 右括号还可以使用的个数 :return: """ if left == 0 and right == 0: res.append(cur_str) return if right < left: return if left > 0: dfs(cur_str + '(', left - 1, right) if right > 0: dfs(cur_str + ')', left, right - 1) dfs(cur_str, n, n) return res """ For Example: input: n = 3 output: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] """ n = 3 solution = Solution() result = solution.generateParenthesis(n) print('输出为：', result)方法二： 递循环遍历 题解
执行用时：52 ms, 在所有 Python3 提交中击败了29.10%的用户 内存消耗：13.9 MB, 在所有 Python3 提交中击败了6.06%的用户 from typing import List class Solution: def generateParenthesis(self, n: int) -> List[str]: if n == 0: return [] dp = [None for _ in range(n + 1)] dp[0] = [""] for i in range(1, n + 1): cur = [] for j in range(i): left = dp[j] right = dp[i - j - 1] for s1 in left: for s2 in right: cur.append("(" + s1 + ")" + s2) dp[i] = cur return dp[n] """ For Example: input: n = 3 output: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] """ n = 3 solution = Solution() result = solution.generateParenthesis(n) print('输出为：', result)