Gojava算法之括号生成示例详解

第Gojava算法之括号生成示例详解目录括号生成方法一：深度优先遍历（java）方法一：深度优先遍历（go）

括号生成

数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例1：

输入：n=3

输出：[((())),(()()),(())(),()(()),()()()]

示例2：

输入：n=1

输出：[()]

提示：

1=n=8

方法一：深度优先遍历（java）

首先我们需要知道一个结论，一个合法的括号序列需要满足两个条件：

1、左右括号数量相等

2、任意前缀中左括号数量=右括号数量（也就是说每一个右括号总能找到相匹配的左括号）

题目要求我们生成n对的合法括号序列组合，因此可以考虑使用深度优先搜索

将搜索顺序定义为枚举序列的每一位填什么，那么最终的答案一定是由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);

时间复杂度：o(4^n/n^(1/2))

空间复杂度：o(n)

方法一：深度优先遍历（go）

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

根据题目条件生成一颗树，并对这颗树生枝叶的条件按照题目进行限制。

需要左右括号都大于0个时才可以进行生成树的操作（等于0的特殊情况）

生成树之后生出左节点的条件：左括号的剩余数量大于0

生成树之后生成右节点条件：左括号的剩余数量小于右括号的剩余数量

当左右括号都为0时，为成功出口，此时进行结算，保存结果。

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

时间复杂度：o(