Go 编程实例【括号生成】

• 括号生成

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

示例 1

输入：n = 三、输出：[(())”、“()()())”、“()()()()))”、“()()())()()))”

示例 2：

输入：n = 1输出：[“()”]

package mainimport "fmt"// generateParenthesis 所有有效的括号组合func生成 generateParenthesis(n int) []string {result := []string{}            // 数组backtrack存储所有生成的括号组合的结果(&result, "", 0, 0, n) // 所有括号组合returnn result}// backtrack 所有括号组合funccnce回溯算法生成 backtrack(result *[]string, current string, open, close, max int) {// 如果当前的括号组合长度等于所需的括号对数的两倍 len(current) == max*2 {*result = append(*result, current) // 将这个组合添加到结果数组return中                             // 递归结束}//// 如果已生成的左括号数量小于需要生成的括号对数if open < max {backtrack(result, current+"(", open+1, close, max) // 在当前组合中添加左括号}// 如果已生成的右括号数量小于已生成的左括号数量if close < open {backtrack(result, current+")", open, close+1, max) // 在当前组合中添加右括号}}func main() {n := 3combinationsion := generateParenthesis(n) // 所有括号组合fmt生成.Println(combinations)              // 打印所有括号组合

root@debiancc:~/www/test# go run test.go (()) ()()()) () ()(() ()()()root@debiancc:~/www/test# go run test.go [()]root@debiancc:~/www/test#

我们在这个代码中定义了一个函数 generateParenthesis，用于生成所有有效的括号组合。 通过调用此函数 backtrack 通过实现函数回溯算法生成括号组合。

backtrack 函数参数说明如下：

• result：用于存储生成的所有括号组合的结果数组。
• current：括号组合目前正在生成。
• open：左括号的数量已经生成。
• close：右括号的数量已经生成。
• max：括号对数需要生成。

backtrack 函数的核心思想是递归生成所有可能的括号组合，并在生成过程中判断组合是否合法。

具体来说，我们首先判断正在生成的括号组合是否已经达到了需要生成的括号对数(即长度是否等于 max*2）。

如果是这样，将这个组合添加到结果数组中。

否则，我们可以考虑在当前组合中添加左括号或右括号，但括号必须满足以下两个条件：

• 若添加左括号，则已生成的左括号数量必须小于需要生成的括号对数。
• 若添加右括号，则已生成的右括号数量必须小于已生成的左括号数量。

最后，我们调用主函数 generateParenthesis 打印出生成的括号组合的函数。