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

来到golang学习网的大家，相信都是编程学习爱好者，希望在这里学习Golang相关编程知识。下面本篇文章就来带大家聊聊《Gojava算法之括号生成示例详解》，介绍一下算法、Java、括号生成，希望对大家的知识积累有所帮助，助力实战开发！

括号生成

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

• 示例 1：

输入：n = 3

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

• 示例 2：

输入：n = 1

输出：["()"]  

提示：

1

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

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

1、左右括号数量相等

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

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

将搜索顺序定义为枚举序列的每一位填什么，那么最终的答案一定是由n个左括号和n个右括号组成。

class Solution {
    public List<string> generateParenthesis(int n) {
        List<string> ans = new ArrayList<string>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }
    public void backtrack(List<string> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open 
<p>时间复杂度：o(4^n / n^(1/2))</p>
<p>空间复杂度：o(n)</p>
<h2>方法一：深度优先遍历（go）</h2>
<p>具体方法分析已在上文中表述</p>
<p>根据题目条件生成一颗树，并对这颗树生枝叶的条件按照题目进行限制。</p>
<p>需要左右括号都大于0个时才可以进行生成树的操作（等于0的特殊情况）</p>
<p>生成树之后生出左节点的条件：左括号的剩余数量大于0</p>
<p>生成树之后生成右节点条件：左括号的剩余数量 小于 右括号的剩余数量</p>
<p>当左右括号都为0时，为成功出口，此时进行结算，保存结果。</p>
<pre class="brush:go;">	var ans []string
	var backtrack func([]byte, int, int)
	backtrack = func(bytes []byte, left int, right int) {
		if len(bytes) == 2*n {
			ans = append(ans, string(bytes))
			return
		}
		if left 
<p>时间复杂度：o(4^n / n^(1/2))</p>
<p>空间复杂度：o(n)</p>
<p>理论要掌握，实操不能落！以上关于《Gojava算法之括号生成示例详解》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！</p>