22 括号生成

题目描述#

给定一个整数 n，表示需要生成 n 对括号。要求返回所有可能的、并且有效的括号组合。

有效括号组合需要满足：任意位置之前的右括号数量不能超过左括号数量，并且最终左右括号数量都等于 n。

括号一多就容易盯着屏幕发愣，所以先抓住“前缀合法”这张照片～

思路#

这题可以把生成过程看成一棵回溯搜索树：每一步都尝试往当前字符串 path 后面添加一个左括号或右括号。open 记录当前已经放了多少个左括号，close 记录当前已经放了多少个右括号。嘿嘿，就像一边拍一边检查构图，括号一旦摆歪了，马上剪掉这条分支。

有效括号有两个关键限制。第一，左括号最多只能放 n 个，所以当 open > n 时说明已经超过目标，可以直接返回。第二，任意前缀里的右括号数量不能大于左括号数量，否则这个前缀已经无法成为合法括号串，所以当 close > open 时也要剪枝。

当 open == close == n 时，说明左右括号都用完了，并且整个路径始终满足合法前缀条件，这时就找到了一个答案。递归时如果 open < n，可以继续添加左括号；如果 close < open，说明当前还有未匹配的左括号，才可以添加右括号。没错没错，回溯题的精髓就是“能走才走，走错就及时回头”。

时间复杂度与合法括号组合数量有关，结果数量是第 n 个卡特兰数，每个结果长度为 2n；额外空间主要来自递归栈和当前路径字符串，约为 O(n)，不计返回结果。

记住啦：左括号负责开路，右括号只能跟上，别抢跑就好！

思维边界#

前缀合法性：生成过程中的任意前缀都必须满足 close <= open，否则后续无法补救。
数量上限：左括号最多放 n 个，右括号最终也必须放 n 个。
剪枝时机：发现 open > n 或 close > open 时立即返回，减少无效搜索。
终止条件：只有 open == close == n 时，当前路径才是完整有效答案。
选择约束：左括号在 open < n 时可放，右括号在 close < open 时可放。

代码#

func generateParenthesis(n int) []string {
	// 回溯 + 剪枝
	var dfs func(string, int, int)
	ans := []string{}
	dfs = func(path string, open, close int) {
		// open为左括号的数量 close为右括号的数量
		// 1. 如果open > n 说明左括号的数量比目标大，剪枝
		// 2. 如果close > open 说明右括号的数量大于左括号的数量，剪枝
		if open > n {
			return
		}
		if close > open {
			return
		}
		// 3. 如果close == open == n 说明找到了答案，保存当前路径到答案中
		if close == open && close == n {
			ans = append(ans, path)
			return
		}
		if open < n {
			dfs(path+"(", open+1, close)
		}
		if close < open {
			dfs(path+")", open, close+1)
		}

	}
	dfs("", 0, 0)
	return ans
}