22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
1
2
| 输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
|
示例 2：
DFS
维护一个 leftNum 来表示之前剩余的、没有被匹配到的左括号个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func generateParenthesis(n int) []string {
count := n * 2
res := make([]string, 0)
var dfs func(quotes []byte, layer, leftNum int) // leftNum 表示之前剩余多少个没有被匹配到的左括号
dfs = func(quotes []byte, layer, leftNum int) {
if layer == count {
if leftNum == 0 {
res = append(res, string(quotes))
}
return
}
if leftNum >= 1 {
dfs(append(quotes, ')'), layer+1, leftNum-1)
}
dfs(append(quotes, '('), layer+1, leftNum+1)
}
dfs([]byte{}, 0, 0)
return res
}
|
⭐ 更加标准的 DFS 回溯
回溯法还原变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func generateParenthesis(n int) []string {
count := n * 2
res := make([]string, 0)
var dfs func(quotes []byte, layer, leftNum int) // leftNum 表示之前剩余多少个没有被匹配到的左括号
dfs = func(quotes []byte, layer, leftNum int) {
if layer == count {
if leftNum == 0 {
// 这里不用 copy, 因为 string 函数直接深拷贝了
res = append(res, string(quotes))
}
return
}
if leftNum >= 1 {
quotes = append(quotes, ')')
dfs(quotes, layer+1, leftNum-1)
quotes = quotes[:len(quotes)-1]
}
quotes = append(quotes, '(')
dfs(quotes, layer+1, leftNum+1)
quotes = quotes[:len(quotes)-1]
}
dfs([]byte{}, 0, 0)
return res
}
|
DP
题解：https://leetcode-cn.com/problems/generate-parentheses/solution/zui-jian-dan-yi-dong-de-dong-tai-gui-hua-bu-lun-da/
好屌！
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 {
if n == 1 {
return []string{"()"}
}
dp := [][]string{{""}, {"()"}}
for i := 2; i <= n; i++ {
dpi := make([]string, 0) // dp[i]
for p := 0; p <= i-1; p++ {
q := i - 1 - p
// 遍历dp[p]和dp[q]中的所有组合
for _, quotes1 := range dp[p] {
for _, quotes2 := range dp[q] {
dpi = append(dpi, "("+quotes1+")"+quotes2)
}
}
}
dp = append(dp, dpi)
}
return dp[n]
}
|
