Gojava算法之括號生成示例詳解

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

括號生成

數(shù)字n代表生成括號的對數(shù)，請你設(shè)計一個函數(shù)，用于能夠生成所有可能的并且有效的括號組合。

示例1：

輸入：n=3

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

示例2：

輸入：n=1

輸出：[()]

提示：

1=n=8

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

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

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

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

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

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

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);

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

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

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

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

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

需要左右括號都大于0個時才可以進行生成樹的操作（等于0的特殊情況）

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

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

當(dāng)左右括號都為0時，為成功出口，此時進行結(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

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