括号生成是回溯法的入门题，完整解法二十来行，回溯该有的动作它一个不少。
把这套动作嚼透了，后面的子集、排列、组合，走的都是同一套骨架。
把"有效"两个字拆开
题目只提了一句要求：
生成所有可能的并且有效的括号组合。
前半句好办，把2n个字符排成一排就行，难点全在"有效"两个字上。
n = 3时有 3 个左括号和 3 个右括号，随便排的话是C(6,3) = 20种排法。
可答案只有 5 个。
剩下 15 种犯的是同一个错：
从左往右读到某个位置时，右括号出现的次数已经超过了左括号。
比如")("这样的开头，第一个字符是右括号，它前面没有任何左括号，这个括号永远配不上对。
所以"有效"落在一条很朴素的规则上：
从左往右读，读到的任何一刻，已经出现的
)都不能比(多。
记住这一条，往后每放一个字符，能不能放，用它一查就知道。
把拼串想成走岔路口
为了讲得顺，下面把"拼字符串"说成"在一块白板上一个字一个字地写"。
规则一个字没改，只是叫法变了。
白板上写着正在拼的那个串。
手上还有两个计数器，一个记已经写了几个(，一个记已经写了几个)。
每走到一个岔路口，面前只有两个出口：
| 出口 | 干什么 | 什么时候能走 |
|---|---|---|
| A | 往后接一个( | 左括号还没用完 |
| B | 往后接一个) | 右括号数量比左括号少 |
出口 B 的条件，就是那条规则的代码版。
“右括号比左括号少"和"读到的任何一刻右括号的数量不超过左括号”，说的是同一件事。
按这两个出口一路走下去，一条路走到头，就是白板上写满2n个字符。
这时候手上的串一定合法，收进答案。
三个变量，两个出口
落到代码上，整个过程一直握着三样东西：
| 变量 | 含义 |
|---|---|
cur | 正在拼的串 |
open | 已经写了几个( |
close | 已经写了几个) |
每走到一个岔路口，两个出口对应两条判断：
if(open<max){...}// 出口 A：左括号还没用完if(close<open){...}// 出口 B：右括号不能比左括号多两条判断都不成立的时候，说明左括号已经用完，右括号也已经和左括号一样多，串正好写满，这条路走到了头。
手画一遍 n = 2 的决策树
max = 2，写满 4 个字符就算一条路走完。
每个节点后面标的是(open, close)。
每一步都在做同一件事。
看看两个出口哪个能走，能走就走出去，走完再退回来。
- 从
"(("出发：open = 2 = max，出口 A 走不了；close = 0 < 2，还能走出口 B，得到"(()" - 从
"()"出发：open = 1 < 2，可以接(，得到"()(" - 从
"()("出发：open = 2，出口 A 走不了；close = 1 < 2，接上)，得到"()()"，长度到了 4，收进答案
结果["(())", "()()"]，和n = 2的标准答案一致。
n = 3时规则完全不变，只是目标长度变成6，走到头的路正好 5 条，就是示例里那 5 个串。
"擦掉最后一笔"是干嘛的
cur.append('(');backtrack(ans,cur,open+1,close,max);cur.deleteCharAt(cur.length()-1);// ← 这一行全题最容易被忽略、又最不能少的就是这一行。
关键在于，cur** 是外面传进来的同一个对象，整棵树共用一份**，每层递归拿到的都是它本身。
回到白板上写字的比方：
拿一支笔，走完一条路要退回路口去试另一条路，就得把刚写的那一笔擦掉，白板才能恢复成刚走到路口时的样子。
不擦的话，白板上的字只增不减，一路膨胀下去，长度很快超过2n。
而结束条件写的是"长度等于2n"，是个相等判断，长度一旦越过这个数就再也不会相等，后面的路永远等不到收答案的那一刻。
所以"加一步、递归、撤一步"三个动作绑在一起，缺一不可。
翻译成 Java 代码
前面讲过的做法，写成代码就是这么几行：
classSolution{publicList<String>generateParenthesis(intn){List<String>ans=newArrayList<String>();// 从空串、两个计数器归零开始搜backtrack(ans,newStringBuilder(),0,0,n);returnans;}// ans 装答案// cur 正在拼的串（全树共用同一个对象）// open 已经用了几个 '('// close 已经用了几个 ')'// max 就是 n，一共要几对publicvoidbacktrack(List<String>ans,StringBuildercur,intopen,intclose,intmax){// 位置填满了，2n 个字符全用完，这时候的串一定合法if(cur.length()==max*2){ans.add(cur.toString());// 存一份快照，不是存这个对象的引用return;}// 出口 A：左括号还有剩，可以放一个if(open<max){cur.append('(');backtrack(ans,cur,open+1,close,max);cur.deleteCharAt(cur.length()-1);// 撤销这一步}// 出口 B：右括号比左括号少，才能放，否则会出现非法前缀if(close<open){cur.append(')');backtrack(ans,cur,open,close+1,max);cur.deleteCharAt(cur.length()-1);// 撤销这一步}}}| 代码 | 大白话 |
|---|---|
cur.length() == max * 2 | 2n 个位置填满了，手上这条路径走完了 |
ans.add(cur.toString()) | 存快照 |
open < max | 左括号还没用完 |
close < open | 右括号不能比左括号多 |
cur.append(...) | 在串的尾巴上接一个字符 |
cur.deleteCharAt(...) | 退回路口前，把刚写的那一笔擦掉 |
C++ 版
同一套思路，C++ 把StringBuilder换成string，加一笔是push_back，擦一笔是pop_back。
classSolution{public:vector<string>generateParenthesis(intn){vector<string>ans;string cur;// 正在拼的串（全树共用同一个对象）// 从空串、两个计数器归零开始搜backtrack(ans,cur,0,0,n);returnans;}// ans 装答案// cur 正在拼的串（全树共用同一个对象）// open 已经用了几个 '('// close 已经用了几个 ')'// max 就是 n，一共要几对voidbacktrack(vector<string>&ans,string&cur,intopen,intclose,intmax){// 位置填满了，2n 个字符全用完，这时候的串一定合法if(cur.size()==max*2){ans.push_back(cur);// 存一份拷贝，不是存这个对象的引用return;}// 出口 A：左括号还有剩，可以放一个if(open<max){cur.push_back('(');backtrack(ans,cur,open+1,close,max);cur.pop_back();// 撤销这一步}// 出口 B：右括号比左括号少，才能放，否则会出现非法前缀if(close<open){cur.push_back(')');backtrack(ans,cur,open,close+1,max);cur.pop_back();// 撤销这一步}}};Python 版
Python 的字符串没法原地改，把字符先攒在一个列表里，收进答案时再拼成串；参数名也换成left和right，避开内置函数open。
classSolution:defgenerateParenthesis(self,n:int)->list[str]:ans=[]# cur 正在拼的串（全树共用同一个列表）# left 已经用了几个 '('# right 已经用了几个 ')'defbacktrack(cur,left,right):# 位置填满了，2n 个字符全用完，这时候的串一定合法iflen(cur)==n*2:ans.append("".join(cur))# 存一份拼好的串，不是存这个列表return# 出口 A：左括号还有剩，可以放一个ifleft<n:cur.append('(')backtrack(cur,left+1,right)cur.pop()# 撤销这一步# 出口 B：右括号比左括号少，才能放，否则会出现非法前缀ifright<left:cur.append(')')backtrack(cur,left,right+1)cur.pop()# 撤销这一步backtrack([],0,0)returnans四个容易写错的地方
cur.toString()不能省
ans声明的是字符串列表，每个位置只收String；
cur是个StringBuilder，直接写ans.add(cur)塞进去，类型对不上，编译就过不了。
而toString()恰好办成了两件事。
它照着cur当下的内容造一条新字符串，收进答案的是这条新串，等于给这一刻的白板拍了张快照。
cur全树只有一份，后面还要接着写、接着擦，要是把cur本身收进ans，白板每变一次，已经收进去的每一条都跟着一起变，到最后全长得一模一样。
deleteCharAt不能省
deleteCharAt干的就是撤销：
把刚接上去的那个字符拿掉。
少了它，所有分支共用一条只增不减的串，回溯就名不副实。
条件是close < open，别写成close < max
写成close < max，只是判断右括号还有没有剩，没有检查手上的左括号够不够配。
open == close的时候它也放行，第一步就能写出")"这样的开头，非法前缀源源不断地混进答案。
open和close回来不用还原
它们是int形参，每层递归都有自己的副本。
这一层写open + 1，传进去的是新值，回来时这一层的open没动过。
整棵树真正共用的只有cur那一个对象，所以只有它需要手动撤销。
数量规律
合法组合的个数有个名字，叫卡特兰数：
| n | 1 | 2 | 3 | 4 | 5 | 8 |
|---|---|---|---|---|---|---|
| 答案个数 | 1 | 2 | 5 | 14 | 42 | 1430 |
题目给的n <= 8，最多 1430 个结果，这样一路搜到底稳稳能过。
时间上，不合法的分支在刚冒头时就剪掉了，树上的每个节点都是合法前缀，只做常数次判断，写一笔、擦一笔也只花常数时间；
收进答案时，每个结果还要复制成一条长度2n的串。
总时间和输出规模同量级，记成O(n × Cₙ)，Cₙ就是上面那张表里第n个卡特兰数。
空间上，递归栈的深度最多2n，每层只存常数个变量，cur最多存2n个字符，这两块合起来是O(n)；
另外还要存下全部结果，Cₙ条、每条长2n，这部分就是输出的体量。
不算结果，额外空间是O(n)；
连结果一起算，总空间也是O(n × Cₙ)。
收个尾
括号生成是回溯法的最小完整样例。
两个计数器管合法性，两个出口管分支，加一步、递归、撤一步。
这套结构能复用的地方比想象中多。
子集、全排列、组合总和、分割字符串，都是同一个动作：
往前走一步，走完退回来，换下一个选择。
把这一道吃透，后面一整片题都是换汤不换药。
