可视化图解算法59：括号生成

原创

用户11589437

修改于 2025-09-04 17:42:34

2010

文章被收录于专栏：数据结构与算法精讲数据结构与算法精讲

牛客网面试笔试 TOP101 | LeetCode 22. 括号生成正数

1. 题目

描述

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为：

"((()))", "(()())", "(())()", "()()()", "()(())"

数据范围：0 ≤n≤10

要求：空间复杂度 O(n)，时间复杂度 O(2n)

示例1

输入：

1

返回值：

["()"]

示例2

输入：

2

返回值：

["(())","()()"]

2. 解题思路

括号的生成可以使用回溯算法完成，结合回溯算法模板，对应的思路如下：

在此过程要特别注意：左括号进行处理节点、递归、回溯，右括号也需要进行相同的操作。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

3. 编码实现

核心代码如下：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @return string字符串一维数组
 */
func generateParenthesis(n int) []string {
  // write code here
  result = make([]string, 0)
  backtracking("", 0, 0, 2*n)
  return result
}

func backtracking(current string, left int, right int, max int) {
  if len(current) == max {
    //2.1 存放结果
    result = append(result, current)
    //2.2 返回
    return
  }

  //1.选择：在本层集合中遍历元素
  //1.1 如果左括号数量小于n，可以尝试添加一个左括号
  if left < max/2 {
    //1.1.1 处理节点（添加一个左括号）
    current = current + "("
    // 1.1.2 递归（尝试再次添加括号）
    backtracking(current, left+1, right, max)
    //1.1.3 回溯，撤销选择（移除刚刚添加的左括号）
    current = current[:len(current)-1]
  }
  //1.2 如果右括号数量小于左括号数量，可以尝试添加一个右括号
  if right < left {
    //1.2.1 处理节点（添加一个右括号）
    current = current + ")"
    // 1.2.2 递归（尝试再次添加括号）
    backtracking(current, left, right+1, max)
    //1.2.3 回溯，撤销选择（移除刚刚添加的右括号）
    current = current[:len(current)-1]
  }
}

var result []string

具体完整代码你可以参考下面视频的详细讲解。