- 正确答案：给定 n 对括号，生成所有合法的括号组合。合法指：任意前缀中左括号数量 ≥ 右括号数量，且总左括号数 = 总右括号数 = n。例如 n=3 时，输出为 ["((()))","(()())","(())()","()(())","()()()"]。 - 解答思路：采用回溯法（深度优先搜索），在构造字符串过程中动态维护当前已使用的左括号数 left 和右括号数 right。约束条件为：（1）left ≤ n：最多用 n 个左括号；（2）right ≤ left：右括号不能多于左括号（否则出现非法前缀，如 "())"）；（3）当 left == right == n 时，得到一个完整合法解，加入结果集。每次递归分支：若 left < n，可添加 '('；若 right < left，可添加 ')'。注意：必须先加 '(' 再考虑 ')'，保证构造顺序可控。 - 深度知识讲解：该问题本质是生成所有长度为 2n 的 Dyck words（Dyck 路径），与卡特兰数 C_n = (1/(n+1)) * C(2n,n) 严格对应，共 C_n 种合法组合。其数学结构等价于： • 从 (0,0) 到 (2n,0) 的格路，每步为 (1,1)（上步，即 '('）或 (1,-1)（下步，即 ')'），且路径不跌破 x 轴； • 二叉树的中序遍历序列（左括号=进入节点，右括号=离开节点）； • 出栈序列问题（n 个元素依次入栈，所有可能的合法出栈序列数）。底层数据结构上，回溯过程隐式使用调用栈（系统栈），空间复杂度 O(n)（递归最大深度为 2n）；显式也可用栈模拟 DFS，但无必要。时间复杂度为 O(4^n / sqrt(n))，即 Θ(C_n × n)，因为共有 C_n 个解，每个解长度为 2n，且生成每个解需 O(1) 均摊（字符追加为 O(1) amortized）。关键实现细节： • 必须用 StringBuilder（或列表拼接）而非字符串拼接，避免 O(n) 字符串拷贝导致整体退化为 O(n·4^n)； • 剪枝至关重要：right < left 才能加 ')'，否则提前终止，这是保证合法性的核心守卫； • 该算法属于“构造型回溯”，区别于“决策型回溯”（如 N 皇后），其状态转移由计数变量完全刻画，无需 visited 数组或哈希去重。 - 伪代码： ``` function generateParenthesis(n): result = [] current = [] // 使用字符列表，支持 O(1) append/pop function backtrack(left, right): if len(current) == 2 * n: result.append(join(current)) return if left < n: append '(' to current backtrack(left + 1, right) pop last character // 回溯 if right < left: append ')' to current backtrack(left, right + 1) pop last character // 回溯 backtrack(0, 0) return result ``` - Java 实现（关键优化版）： ``` public List generateParenthesis(int n) { List res = new ArrayList<>(); backtrack(res, new StringBuilder(), 0, 0, n); return res; } private void backtrack(List res, StringBuilder sb, int left, int right, int n) { if (sb.length() == 2 * n) { res.add(sb.toString()); return; } if (left < n) { sb.append('('); backtrack(res, sb, left + 1, right, n); sb.setLength(sb.length() - 1); // O(1) 截断，优于 deleteCharAt } if (right < left) { sb.append(')'); backtrack(res, sb, left, right + 1, n); sb.setLength(sb.length() - 1); } } ``` - 扩展知识点： 1. 迭代解法：可用 BFS 层序生成，每层表示固定长度的候选字符串，用队列存储（state = (s, left, right)），但空间开销更大； 2. 动态规划解法：设 dp[i] 表示 i 对括号的所有解，则 dp[i] = ∑_{j=0}^{i-1} [ "(" + dp[j] + ")" + dp[i-1-j] ]，体现卡特兰递推关系； 3. 位运算解法：将每个括号序列映射为 2n 位二进制数（0='(', 1=')'），枚举所有 C(2n,n) 个含 n 个 1 的数，并用前缀和校验合法性，时间复杂度更高但适合理解组合本质； 4. 与编译原理关联：该生成器可视为上下文无关文法 S → ε | (S)S 的最左推导枚举，文法 G = ({S}, {'(', ')'}, {S→ε | S→(S)S}, S) 是无歧义的，且恰好生成所有合法括号串。

高德LLM大模型一面-实习面经

全站热榜

创作者周榜