LeetCode-22. 括号生成 - sheep44044的小站

回溯#

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

1
输入：n = 3
2
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

1
输入：n = 1
2
输出：["()"]

1
func generateParenthesis(n int) []string {
2
    res := []string{}
3
    path := []byte{}
4

5
    var backtrack func(left, right int)
6
    backtrack = func(left, right int) {
7
        if len(path) == n * 2 {
8
            res = append(res, string(path))
9
            return
10
        }
11

12
        if left < n {
13
            path = append(path, '(')
14
            backtrack(left+1,right)
15
            path = path[:len(path)-1]
16
        }
17

18
        if right < left {
19
            path = append(path, ')')
20
            backtrack(left,right+1)
21
            path = path[:len(path)-1]
22
        }
23
    }
24

25
    backtrack(0,0)
26
    return res
27
}