LeetCode 22. Generate Parentheses 题解

LeetCode 22. Generate Parentheses 题解题目描述数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。示例 1输入n 3 输出[((())),(()()),(())(),()(()),()()()]示例 2输入n 1 输出[()]解题思路这是一个经典的回溯算法问题。需要生成所有有效的括号组合。有效括号的条件左括号数量等于右括号数量都等于 n任何前缀中左括号数量 右括号数量回溯策略如果左括号数量 n可以添加左括号如果右括号数量 左括号数量可以添加右括号当左右括号数量都等于 n 时得到一个有效组合代码实现def generateParenthesis(n): result [] def backtrack(current, left, right): # 如果左右括号都用完得到一个有效组合 if left 0 and right 0: result.append(current) return # 如果还可以添加左括号 if left 0: backtrack(current (, left - 1, right) # 如果右括号数量小于左括号数量可以添加右括号 if right left: backtrack(current ), left, right - 1) backtrack(, n, n) return result复杂度分析时间复杂度O(4^n / √n)卡塔兰数的渐近界空间复杂度O(n)递归栈的深度动态规划解法也可以使用动态规划解决def generateParenthesis(n): if n 0: return [] dp [[] for _ in range(n 1)] dp[0] [] for i in range(1, n 1): for j in range(i): for left in dp[j]: for right in dp[i - 1 - j]: dp[i].append(f({left}){right}) return dp[n]测试案例# 测试案例 1 assert sorted(generateParenthesis(3)) sorted([((())),(()()),(())(),()(()),()()()]) # 测试案例 2 assert generateParenthesis(1) [()] # 测试案例 3 assert sorted(generateParenthesis(2)) sorted([(()),()()]) # 测试案例 4 assert generateParenthesis(0) []总结本题是回溯算法的经典应用也是卡塔兰数的经典问题。关键点有效括号的两个条件数量相等、任何前缀左括号 右括号回溯的剪枝策略只有右括号数量 左括号数量时才添加右括号卡塔兰数n 对括号的有效组合数为第 n 个卡塔兰数通过本题可以深入理解回溯算法的剪枝技巧以及卡塔兰数在组合问题中的应用。