詳解一道高頻算法題：括號(hào)生成

題目描述

給出 n 代表生成括號(hào)的對(duì)數(shù)，請你寫出一個(gè)函數(shù)，使其能夠生成所有可能的并且有效的括號(hào)組合。

例如，給出 n = 3，生成結(jié)果為：

[ "((()))", "(()())", "(())()", "()(())", "()()()" ] 題目解析

方法一：回溯算法（深度優(yōu)先遍歷）

如果完成一件事情有很多種方法，并且每一種方法分成若干步驟，那多半就可以使用“回溯”算法完成。

“回溯”算法的基本思想是“嘗試搜索”，一條路如果走不通（不能得到想要的結(jié)果），就回到上一個(gè)“路口”，嘗試走另一條路。

因此，“回溯”算法的時(shí)間復(fù)雜度一般不低。如果能提前分析出，走這一條路并不能得到想要的結(jié)果，可以跳過這個(gè)分支，這一步操作叫“剪枝”。

做“回溯”算法問題的基本套路是：

1、使用題目中給出的示例，畫樹形結(jié)構(gòu)圖，以便分析出遞歸結(jié)構(gòu)；

一般來說，樹形圖不用畫完，就能夠分析出遞歸結(jié)構(gòu)和解題思路。

2、分析一個(gè)結(jié)點(diǎn)可以產(chǎn)生枝葉的條件、遞歸到哪里終止、是否可以剪枝、符合題意的結(jié)果在什么地方出現(xiàn)（可能在葉子結(jié)點(diǎn)，也可能在中間的結(jié)點(diǎn)）；

3、完成以上兩步以后，就要編寫代碼實(shí)現(xiàn)上述分析的過程，使用代碼在畫出的樹形結(jié)構(gòu)上搜索符合題意的結(jié)果。

在樹形結(jié)構(gòu)上搜索結(jié)果集，使用的方法是執(zhí)行一次“深度優(yōu)先遍歷”。在遍歷的過程中，可能需要使用“狀態(tài)變量”。

（“廣度優(yōu)先遍歷”當(dāng)然也是可以的，請參考方法二。）

我們以 n = 2 為例，畫樹形結(jié)構(gòu)圖。

題解配圖(1)

畫圖以后，可以分析出的結(jié)論：

左右都有可以使用的括號(hào)數(shù)量，即嚴(yán)格大于 0 的時(shí)候，才產(chǎn)生分支；

左邊不受右邊的限制，它只受自己的約束；

右邊除了自己的限制以外，還收到左邊的限制，即：右邊剩余可以使用的括號(hào)數(shù)量一定得在嚴(yán)格大于左邊剩余的數(shù)量的時(shí)候，才可以“節(jié)外生枝”；

在左邊和右邊剩余的括號(hào)數(shù)都等于 0 的時(shí)候結(jié)算。

參考代碼如下：

publicclassSolution{ publicListgenerateParenthesis(intn){ Listres=newArrayList<>(); //特判 if(n==0){ returnres; } //執(zhí)行深度優(yōu)先遍歷，搜索可能的結(jié)果 dfs("",n,n,res); returnres; } /** *@paramcurStr當(dāng)前遞歸得到的結(jié)果 *@paramleft左括號(hào)還有幾個(gè)沒有用掉 *@paramright右邊的括號(hào)還有幾個(gè)沒有用掉 *@paramres結(jié)果集 */ privatevoiddfs(StringcurStr,intleft,intright,Listres){ //因?yàn)槭沁f歸函數(shù)，所以先寫遞歸終止條件 if(left==0&&right==0){ res.add(curStr); return; } //因?yàn)槊恳淮螄L試，都使用新的字符串變量，所以沒有顯式的回溯過程 //在遞歸終止的時(shí)候，直接把它添加到結(jié)果集即可，與「力扣」第46題、第39題區(qū)分 //如果左邊還有剩余，繼續(xù)遞歸下去 if(left>0){ //拼接上一個(gè)左括號(hào)，并且剩余的左括號(hào)個(gè)數(shù)減1 dfs(curStr+"(",left-1,right,res); } //什么時(shí)候可以用右邊？例如，(((((()，此時(shí) left < right， ????????//?不能用等號(hào)，因?yàn)橹挥邢绕戳俗罄ㄌ?hào)，才能拼上右括號(hào) ????????if?(right?>0&&left

如果我們不用減法，使用加法，即 left 表示“左括號(hào)還有幾個(gè)沒有用掉”，right 表示“右括號(hào)還有幾個(gè)沒有用掉”，可以畫出另一棵遞歸樹。

題解配圖(2)

參考代碼如下：

publicclassSolution{ //方法 2：用加法 publicListgenerateParenthesis(intn){ Listres=newArrayList<>(); //特判 if(n==0){ returnres; } //這里的dfs是隱式回溯 dfs("",0,0,n,res); returnres; } /** *@paramcurStr當(dāng)前遞歸得到的結(jié)果 *@paramleft左括號(hào)用了幾個(gè) *@paramright右括號(hào)用了幾個(gè) *@paramn左括號(hào)、右括號(hào)一共用幾個(gè) *@paramres結(jié)果集 */ privatevoiddfs(StringcurStr,intleft,intright,intn,Listres){ //因?yàn)槭沁f歸函數(shù)，所以先寫遞歸終止條件 if(left==n&&right==n){ res.add(curStr); return; } //如果左括號(hào)還沒湊夠，繼續(xù)湊 if(left right， //不能用等號(hào)，因?yàn)橹挥邢绕戳俗罄ㄌ?hào)，才能拼上右括號(hào) if(rightright){ //拼接上一個(gè)右括號(hào)，并且剩余的右括號(hào)個(gè)數(shù)減1 dfs(curStr+")",left,right+1,n,res); } } }

方法二：廣度優(yōu)先遍歷

還是上面的題解配圖（1），使用廣度優(yōu)先遍歷，結(jié)果集都在最后一層，即葉子結(jié)點(diǎn)處得到所有的結(jié)果集，編寫代碼如下。

publicclassSolution{ classNode{ /** *當(dāng)前得到的字符串 */ privateStringres; /** *剩余左括號(hào)數(shù)量 */ privateintleft; /** *剩余右括號(hào)數(shù)量 */ privateintright; publicNode(Stringres,intleft,intright){ this.res=res; this.left=left; this.right=right; } @Override publicStringtoString(){ return"Node{"+ "res='"+res+'''+ ",left="+left+ ",right="+right+ '}'; } } publicListgenerateParenthesis(intn){ Listres=newArrayList<>(); if(n==0){ returnres; } Queuequeue=newLinkedList<>(); queue.offer(newNode("",n,n)); //總共需要拼湊的字符總數(shù)是2*n n=2*n; while(n>0){ intsize=queue.size(); for(inti=0;i0){ queue.offer(newNode(curNode.res+"(",curNode.left-1,curNode.right)); } if(curNode.right>0&&curNode.left

方法三：動(dòng)態(tài)規(guī)劃

第 1 步：定義狀態(tài) dp[i]

使用 i 對(duì)括號(hào)能夠生成的組合。

注意：每一個(gè)狀態(tài)都是列表的形式。

第 2 步：狀態(tài)轉(zhuǎn)移方程：

i 對(duì)括號(hào)的一個(gè)組合，在 i - 1 對(duì)括號(hào)的基礎(chǔ)上得到；

i 對(duì)括號(hào)的一個(gè)組合，一定以左括號(hào) "(" 開始（不一定以 ")" 結(jié)尾），為此，我們可以枚舉右括號(hào) ")" 的位置，得到所有的組合；

枚舉的方式就是枚舉左括號(hào) "(" 和右括號(hào) ")" 中間可能的合法的括號(hào)對(duì)數(shù)，而剩下的合法的括號(hào)對(duì)數(shù)在與第一個(gè)左括號(hào) "(" 配對(duì)的右括號(hào) ")" 的后面，這就用到了以前的狀態(tài)。

狀態(tài)轉(zhuǎn)移方程是：

dp[i] = "(" + dp[可能的括號(hào)對(duì)數(shù)] + ")" + dp[剩下的括號(hào)對(duì)數(shù)]

“可能的括號(hào)對(duì)數(shù)” 與 “剩下的括號(hào)對(duì)數(shù)” 之和得為 i，故“可能的括號(hào)對(duì)數(shù)” j 可以從 0 開始，最多不能超過 i， 即 i - 1；

“剩下的括號(hào)對(duì)數(shù)” + j = i - 1，故 “剩下的括號(hào)對(duì)數(shù)” = i - j - 1。

整理得：

dp[i] = "(" + dp[j] + ")" + dp[i- j - 1] , j = 0, 1, ..., i - 1

第 3 步：思考初始狀態(tài)和輸出：

初始狀態(tài)：因?yàn)槲覀冃枰?0 對(duì)括號(hào)這種狀態(tài)，因此狀態(tài)數(shù)組 dp 從 0 開始，0 個(gè)括號(hào)當(dāng)然就是 [""]。
輸出：dp[n] 。
這個(gè)方法暫且就叫它動(dòng)態(tài)規(guī)劃，這么用也是很神奇的，它有下面兩個(gè)特點(diǎn)：

1、自底向上：從小規(guī)模問題開始，逐漸得到大規(guī)模問題的解集；

2、無后效性：后面的結(jié)果的得到，不會(huì)影響到前面的結(jié)果。

publicclassSolution{ //把結(jié)果集保存在動(dòng)態(tài)規(guī)劃的數(shù)組里 publicListgenerateParenthesis(intn){ if(n==0){ returnnewArrayList<>(); } //這里dp數(shù)組我們把它變成列表的樣子，方便調(diào)用而已 List>dp=newArrayList<>(n); Listdp0=newArrayList<>(); dp0.add(""); dp.add(dp0); for(inti=1;i<=?n;?i++)?{ ????????????Listcur=newArrayList<>(); for(intj=0;jstr1=dp.get(j); Liststr2=dp.get(i-1-j); for(Strings1:str1){ for(Strings2:str2){ //枚舉右括號(hào)的位置 cur.add("("+s1+")"+s2); } } } dp.add(cur); } returndp.get(n); } }