yankewei
commented
3 years ago 递归
简单点说就是把所有的可能都列出来
func generateParenthesis(n int) []string {
return generate(n,"(", [2]int{1,0}, &[]string{})
}
func generate(n int, cur string, used [2]int, set *[]string) []string {
if used[0] > n || used[1] > n { // 已经把(用掉了n或者把)用掉了n, 那肯定不是一个有效的括号组合
return *set
}
if len(cur) == n * 2 { // 括号已经用完
if invalid(cur) {
*set = append(*set, cur)
seen[cur] = struct{}{}
}
} else {
generate(n, cur + "(", [2]int{used[0]+1, used[1]}, set, seen)
generate(n, cur + ")", [2]int{used[0], used[1]+1}, set, seen)
}
return *set
}
func invalid(str string) bool {
var stack []int32
for _, v := range str {
if len(stack) == 0 {
stack = append(stack, v)
continue
}
if v == ')' && stack[len(stack)-1] == '('{
stack = stack[:len(stack)-1]
} else {
stack = append(stack, v)
}
}
return len(stack) == 0
}回溯
再上边暴力递归的情况下，有一些数据没有必要再进入下一层循环。
func generateParenthesis(n int) []string {
return generate(n,"(", [2]int{1,0}, &[]string{})
}
func generate(n int, cur string, used [2]int, set *[]string) []string {
if used[0] > n || used[1] > n { // 已经把(用掉了n或者把)用掉了n, 那肯定不是一个有效的括号组合
return *set
}
if len(cur) == n * 2 { // 括号已经用完
if invalid(cur) {
*set = append(*set, cur)
}
} else {
// 如果左括号还没用完，那就用一个
if used[0] < n {
generate(n, cur + "(", [2]int{used[0]+1, used[1]}, set)
}
// 要用右括号的前提是左括号比右括号用的多，否则使用右括号显然不是一个有效的括号
if used[0] > used[1] {
generate(n, cur + ")", [2]int{used[0], used[1]+1}, set)
}
}
return *set
}
func invalid(str string) bool {
var stack []int32
for _, v := range str {
if len(stack) == 0 {
stack = append(stack, v)
continue
}
if v == ')' && stack[len(stack)-1] == '('{
stack = stack[:len(stack)-1]
} else {
stack = append(stack, v)
}
}
return len(stack) == 0
}
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
示例 2：
提示：
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/generate-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。