22. 括号生成

题目描述：

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

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

---

解题分析及思路：

方法：深度优先搜索

思路：

本题可采用深度优先搜索（DFS）结合剪枝策略求解，核心思路是通过递归逐步构建括号序列，并在生成过程中确保有效性。

具体实现逻辑如下：

1. 递归状态设计：

   • 使用bytes数组存储当前正在构建的括号序列
   • 用leftNumber和rightNumber分别记录已使用的左、右括号数量
   • 结果通过外部变量res收集所有有效组合

2. 递归终止条件： 当左括号和右括号的数量都等于n时，说明已生成一个完整有效的括号组合，将其转换为字符串后存入结果集。

3. 剪枝与递归扩展：

   • 左括号扩展：若当前左括号数量小于n，可添加左括号并递归（确保不会生成超过n对的左括号）
   • 右括号扩展：若当前右括号数量小于左括号数量，可添加右括号并递归（保证括号有效性，避免出现右括号多于左括号的无效情况）

4. 初始调用： 从空序列、0 个左括号和 0 个右括号开始递归，逐步构建所有可能的有效组合。

func generateParenthesis(n int) []string {
	var res []string  // 用于存储结果集
	var dfs func(bytes []byte, leftNumber, rightNumber int)
	
	// 定义DFS函数
	dfs = func(bytes []byte, leftNumber, rightNumber int) {
		// 递归终止条件：左右括号数量都达到n
		if leftNumber == n && rightNumber == n {
			res = append(res, string(bytes))
			return
		}
		
		// 如果左括号数量小于n，可以添加左括号
		if leftNumber < n {
			dfs(append(bytes, '('), leftNumber+1, rightNumber)
		}
		
		// 如果右括号数量小于左括号数量，可以添加右括号
		if rightNumber < leftNumber {
			dfs(append(bytes, ')'), leftNumber, rightNumber+1)
		}
	}
	
	// 从空字符串、0个左括号、0个右括号开始递归
	dfs([]byte{}, 0, 0)
	return res
}

复杂度：

• 时间复杂度：O(4^n / √n)
• 空间复杂度：O(n)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:4.5 MB,击败了91.88% 的Go用户