22. Generate Parentheses #
题目 #
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
题目大意 #
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
解题思路 #
- 这道题乍一看需要判断括号是否匹配的问题，如果真的判断了，那时间复杂度就到 O(n * 2^n)了，虽然也可以 AC，但是时间复杂度巨高。
- 这道题实际上不需要判断括号是否匹配的问题。因为在 DFS 回溯的过程中，会让
(和)成对的匹配上的。
代码 #
package leetcode
func generateParenthesis(n int) []string {
if n == 0 {
return []string{}
}
res := []string{}
findGenerateParenthesis(n, n, "", &res)
return res
}
func findGenerateParenthesis(lindex, rindex int, str string, res *[]string) {
if lindex == 0 && rindex == 0 {
*res = append(*res, str)
return
}
if lindex > 0 {
findGenerateParenthesis(lindex-1, rindex, str+"(", res)
}
if rindex > 0 && lindex < rindex {
findGenerateParenthesis(lindex, rindex-1, str+")", res)
}
}