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