leetcode 22. 括号生成

题目描述

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:


[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

题解

递归,左括号小于n时递归,右括号小于左括号时递归,左右括号数量为n时停止递归

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func generateParenthesis(n int) []string {
res := make([]string, 0)
if n == 0 {
return res
}
generate(&res, "", n, 0)
return res
}

func generate(arr *[]string, str string, left, right int) {
if left == 0 && right == 0 {
*arr = append(*arr, str)
return
}
if left > 0 {
generate(arr, str+"(", left-1, right+1)
}
if right > 0 {
generate(arr, str+")", left, right-1)
}
}