回溯练习题
# 面试题 08.09. 括号(Medium) (opens new window)
打印n对括号的所有合法的组合。
# 样例
Input: n = 3
Output:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 代码
def backtracking(l, r, ans, tmp):
if l == 0 and r == 0: # 找到
ans.append(tmp)
return
if l > r : # 数目不匹配
return
if l > 0:
backtracking(l - 1, r, ans, tmp + '(')
if r > 0:
backtracking(l, r - 1, ans, tmp + ')')
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
backtracking(n, n, ans, '')
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func backtracking(l int, r int, tmp string) {
if l == 0 && r == 0 { // 找到答案
ans = append(ans, tmp)
return
}
if l > r { // 括号没有一一匹配
return
}
if l > 0 {
backtracking(l - 1, r, tmp + "(")
}
if r > 0 {
backtracking(l, r - 1, tmp + ")")
}
}
var ans []string
func generateParenthesis(n int) []string {
ans = []string{}
backtracking(n, n, "")
return ans
}
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
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54