括号生成
📌 定义
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例:
输入: n = 3
输出: ["((()))","(()())","(())()","()(())","()()()"]
输入: n = 1
输出: ["()"]
输入: n = 2
输出: ["(())","()()"]
核心思路
使用回溯算法，关键是维护括号的有效性：
- 左括号：只要
left < n，就可以添加 - 右括号：只有
right < left时才能添加（保证有效）
Go 代码
Go 实现
func generateParenthesis(n int) []string {
result := []string{}
path := []byte{}
var backtrack func(left, right int)
backtrack = func(left, right int) {
if len(path) == 2*n {
result = append(result, string(path))
return
}
if left < n {
path = append(path, '(')
backtrack(left+1, right)
path = path[:len(path)-1]
}
if right < left {
path = append(path, ')')
backtrack(left, right+1)
path = path[:len(path)-1]
}
}
backtrack(0, 0)
return result
}思路展开
n=3 的决策树:
""
↓
"("
/ \
"((" "()"
/ \ / \
"(((" "(()" "()(" "()()"
↓ ↓ \ ↓ \ ↓
"((())""(()()""(())(""()(()"...
关键约束:
1. left < n: 可以添加左括号
2. right < left: 可以添加右括号
经典题目
- 括号生成 - LeetCode 22
- 有效的括号 - LeetCode 20
- 最长有效括号 - LeetCode 32
相关主题
- 回溯算法 - 返回回溯算法总览