括号生成

递归与回溯

说明

仅在左括号未用完时添加左括号，且右括号数不能超过左括号数。

分析

递归状态由已放入的左右括号数量表示。只在左括号还有余额时增加左括号，且右括号不能超过已有左括号，这样生成过程始终合法。

图解推演

n=2 时，空串不能先放右括号；放一个左括号后才出现两种合法分支。约束 0≤right≤left≤n 保证每个前缀都可配对，长度达到 2n 才输出。仅检查最终左右数量相等会错误接纳以右括号开头的串。

查看图表代码

适用前提与边界

到长度 2n 时得到完整答案，不需要先生成非法串再过滤。

示例输入与调用

fmt.Println(Parentheses(3))

运行输出

[((())) (()()) (())() ()(()) ()()()]

完整 Go 示例

package main

import "fmt"

func Parentheses(n int) []string {
	out := []string{}
	var dfs func(string, int, int)
	dfs = func(s string, l, r int) {
		if len(s) == 2*n {
			out = append(out, s)
			return
		}
		if l < n {
			dfs(s+"(", l+1, r)
		}
		if r < l {
			dfs(s+")", l, r+1)
		}
	}
	dfs("", 0, 0)
	return out
}

func main() {
	fmt.Println(Parentheses(3))
}