知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 09 - 括号生成 ## 题目(LeetCode 22) 给定 n 对括号,生成所有合法的括号组合。 ``` 输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"] ``` ## 大白话理解 你有 n 个左括号和 n 个右括号,排成一个字符串。合法的条件: 1. 任何时候,已用的右括号数量 ≤ 已用的左括号数量(不能先闭合再打开) 2. 最终左右括号各用了 n 个 换个说法:每一步你可以选择放 `(` 或 `)`,但要满足: - 左括号还有剩余才能放 `(` - 已放的左括号比右括号多才能放 `)`(否则就不合法了) ``` n = 2 的决策树: "" / \ "(" ← 只能放 (,不能先放 ) / \ "((" "()" / / "(()" "()( | | "(())" "()()" ``` ## 代码 ```java class Solution { private List<String> result = new ArrayList<>(); public List<String> generateParenthesis(int n) { backtrack(n, 0, 0, new StringBuilder()); return result; } private void backtrack(int n, int open, int close, StringBuilder path) { // 终止条件:用完了所有括号 if (path.length() == 2 * n) { result.add(path.toString()); return; } // 选择 1:放左括号(还有剩余的话) if (open < n) { path.append('('); backtrack(n, open + 1, close, path); path.deleteCharAt(path.length() - 1); } // 选择 2:放右括号(已放的左括号比右括号多的话) if (close < open) { path.append(')'); backtrack(n, open, close + 1, path); path.deleteCharAt(path.length() - 1); } } } ``` ### 两个剪枝条件 ``` open < n: 左括号还没用完,可以继续放 如果 open == n,不能再放左括号了 close < open: 已放的右括号比左括号少,可以放右括号 如果 close == open,再放右括号就不合法了(多出来的 ) 没有 ( 匹配) 这两个条件保证了生成的每个字符串都是合法的 不需要生成后再验证,从源头就杜绝了非法组合 ``` ### 为什么这不是标准的 for 循环模板? 因为每一步只有两个选择(放 `(` 或 `)`),不需要 for 循环遍历选择列表。用两个 if 分支就够了。 本质上和模板是一样的: ```java // 等价于 for (char c : ['(', ')']) { if (c == '(' && open >= n) continue; // 剪枝 if (c == ')' && close >= open) continue; // 剪枝 path.append(c); backtrack(...); path.deleteCharAt(...); } ``` ## 画图模拟(n=2) ``` backtrack(open=0, close=0, "") 放 (: backtrack(1, 0, "(") 放 (: backtrack(2, 0, "((") 放 ): backtrack(2, 1, "(()") 放 ): backtrack(2, 2, "(())") → 收集 ✓ 放 ): backtrack(1, 1, "()") 放 (: backtrack(2, 1, "()(") 放 ): backtrack(2, 2, "()()") → 收集 ✓ 结果:["(())", "()()"] ``` ## 复杂度 - 时间:O(4^n / √n),第 n 个卡特兰数 - 空间:O(n),递归深度 ## 一句话总结 每步选放 `(` 或 `)`,左括号没用完可以放 `(`,左括号比右括号多可以放 `)`。两个条件就是全部的剪枝。 --- 上一篇:[08 - 单词搜索](./08-word-search.md) | 下一篇:[10 - 复原 IP 地址](./10-restore-ip.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入