LeetCode 22.括号生成
题目描述
给定一个整数 n，生成所有由 n 对括号组成的有效括号组合。
有效括号组合需满足如下条件：
- 左括号的数量必须等于右括号的数量。
- 在任何前缀中，左括号的数量不能小于右括号的数量。
示例：
输入：n = 3
输出：
["((()))","(()())","(())()","()(())","()()()"
]
Java 实现解法
java">import java.util.*;public class Solution {public List<String> generateParenthesis(int n) {List<String> result = new ArrayList<>();backtrack(result, "", 0, 0, n);return result;}private void backtrack(List<String> result, String current, int open, int close, int n) {// 如果当前字符串长度达到最大长度，添加到结果列表if (current.length() == n * 2) {result.add(current);return;}// 如果左括号的数量小于 n，可以添加左括号if (open < max) {backtrack(result, current + "(", open + 1, close, n);}// 如果右括号的数量小于左括号的数量，可以添加右括号if (close < open) {backtrack(result, current + ")", open, close + 1, n);}}
}
代码说明
generateParenthesis(int n)：该方法是问题的入口，负责调用回溯函数backtrack()来生成所有合法的括号组合。backtrack(List<String> result, String current, int open, int close, int max)：这是递归函数，负责在字符串current中添加括号，直到构建出一个合法的组合。递归中，open
表示已经添加的左括号数量，close表示已添加的右括号数量，max表示一共可以使用多少对括号。- 递归结束条件：当字符串
current的长度达到2 * n时，表示已经生成了一个合法的括号组合，加入结果列表。- 添加括号的规则：
- 当
open小于n时，可以添加一个左括号。- 当
close小于open时，可以添加一个右括号。
解题思路
本题可以使用回溯（Backtracking）算法来解决。回溯的核心思想是递归地构建括号组合，直到满足条件为止。
递归结构：我们可以用两个计数器来分别追踪已用的左括号和右括号数量。对于每一个位置，若左括号的数量小于
n，就可以添加一个左括号；若右括号的数量小于左括号的数量，就可以添加一个右括号。回溯条件：
- 递归停止的条件是当左括号和右括号的数量都等于
n时，说明生成了一个有效的括号组合。- 递归树的左右分支分别表示在当前位置添加左括号或右括号。
有效性检查：在递归过程中，始终保持左括号的数量不小于右括号的数量。只有在左括号数量小于
n时，才能继续添加左括号；当右括号数量小于左括号数量时，才能继续添加右括号。
复杂度分析
时间复杂度：回溯算法的时间复杂度是指数级的。每个递归调用都有两个选择（加左括号或右括号），最多会递归
2^n次，但由于我们限制了递归的分支，这样的情况不会发生。因此，最终的时间复杂度为O(4^n / sqrt(n))。空间复杂度：空间复杂度主要来自递归调用栈。每一层递归都会用到常数空间，因此，最坏情况下，空间复杂度为
O(n)。
