LeetCode 括号生成题解
LeetCode 括号生成题解
题目描述
数字n代表生成括号的对数，请你写一个函数，使其能够生成所有可能的且有效的括号组合。
示例：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
解题思路
方法：回溯
思路：
- 使用回溯算法来解决这个问题。
- 维护两个计数器：左括号的数量和右括号的数量。
- 从第一个位置开始，尝试所有可能的选择：
- 如果左括号数量小于 n，添加左括号。
- 如果右括号数量小于左括号数量，添加右括号。
- 当左括号数量等于 n 且右括号数量等于 n 时，将路径加入结果列表。
复杂度分析：
- 时间复杂度：O(4^n / sqrt(n))，这是卡特兰数的复杂度。
- 空间复杂度：O(n)，递归调用栈的深度为 2n。
代码实现
方法：回溯
# 括号生成（回溯） def generate_parenthesis(n): result = [] def backtrack(path, left, right): if len(path) == 2 * n: result.append(path) return if left < n: backtrack(path + '(', left + 1, right) if right < left: backtrack(path + ')', left, right + 1) backtrack('', 0, 0) return result # 测试 def test_generate_parenthesis(): n = 3 print(generate_parenthesis(n)) # 输出：['((()))', '(()())', '(())()', '()(())', '()()()'] if __name__ == "__main__": test_generate_parenthesis()测试用例
测试用例 1：基本情况
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
测试用例 2：n=1
输入：n = 1
输出：["()"]
总结
括号生成是一个经典的回溯算法问题，它可以通过回溯算法来高效地解决。
回溯算法的核心思想是：维护左右括号的数量，在选择时确保右括号的数量不超过左括号的数量。
掌握回溯算法的使用方法，对于解决类似的问题非常重要。