Gojava算法之括號(hào)生成示例詳解

第Gojava算法之括號(hào)生成示例詳解目錄括號(hào)生成方法一：深度優(yōu)先遍歷（java）方法一：深度優(yōu)先遍歷（go）

括號(hào)生成

數(shù)字n代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)，用于能夠生成所有可能的并且有效的括號(hào)組合。

示例1：

輸入：n=3

輸出：[((())),(()()),(())(),()(()),()()()]

示例2：

輸入：n=1

輸出：[()]

提示：

1=n=8

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

首先我們需要知道一個(gè)結(jié)論，一個(gè)合法的括號(hào)序列需要滿足兩個(gè)條件：

1、左右括號(hào)數(shù)量相等

2、任意前綴中左括號(hào)數(shù)量=右括號(hào)數(shù)量（也就是說(shuō)每一個(gè)右括號(hào)總能找到相匹配的左括號(hào)）

題目要求我們生成n對(duì)的合法括號(hào)序列組合，因此可以考慮使用深度優(yōu)先搜索

將搜索順序定義為枚舉序列的每一位填什么，那么最終的答案一定是由n個(gè)左括號(hào)和n個(gè)右括號(hào)組成。

classSolution{

publicListStringgenerateParenthesis(intn){

ListStringans=newArrayListString

backtrack(ans,newStringBuilder(),0,0,n);

returnans;

publicvoidbacktrack(ListStringans,StringBuildercur,intopen,intclose,intmax){

if(cur.length()==max*2){

ans.add(cur.toString());

return;

if(openmax){

cur.append('(');

backtrack(ans,cur,open+1,close,max);

cur.deleteCharAt(cur.length()-1);

if(closeopen){

cur.append(')');

backtrack(ans,cur,open,close+1,max);

cur.deleteCharAt(cur.length()-1);

時(shí)間復(fù)雜度：o(4^n/n^(1/2))

空間復(fù)雜度：o(n)

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

具體方法分析已在上文中表述

根據(jù)題目條件生成一顆樹(shù)，并對(duì)這顆樹(shù)生枝葉的條件按照題目進(jìn)行限制。

需要左右括號(hào)都大于0個(gè)時(shí)才可以進(jìn)行生成樹(shù)的操作（等于0的特殊情況）

生成樹(shù)之后生出左節(jié)點(diǎn)的條件：左括號(hào)的剩余數(shù)量大于0

生成樹(shù)之后生成右節(jié)點(diǎn)條件：左括號(hào)的剩余數(shù)量小于右括號(hào)的剩余數(shù)量

當(dāng)左右括號(hào)都為0時(shí)，為成功出口，此時(shí)進(jìn)行結(jié)算，保存結(jié)果。

varans[]string

varbacktrackfunc([]byte,int,int)

backtrack=func(bytes[]byte,leftint,rightint){

iflen(bytes)==2*n{

ans=append(ans,string(bytes))

return

ifleftn{

bytes=append(bytes,'(')

backtrack(bytes,left+1,right)

bytes=bytes[:len(bytes)-1]

ifrightleft{

bytes=append(bytes,')')

backtrack(bytes,left,right+1)

bytes=bytes[:len(bytes)-1]

varcontainer[]byte

backtrack(container,0,0)

returnans

時(shí)間復(fù)雜度：o(