2021-09-19：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
福大大 答案2021-09-19：
递归。
参数1：左括号-右括号的数量。
参数2：左括号剩多少。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
n := 3
ret := generateParenthesis(n)
fmt.Println(ret)
ret2 := generateParenthesis2(n)
fmt.Println(ret2)
}
func generateParenthesis(n int) []string {
path := make([]byte, n<<1)
ans := make([]string, 0)
process(path, 0, 0, n, &ans)
return ans
}
// path 做的决定 path[0....index-1]做完决定的！
// path[index.....] 还没做决定，当前轮到index位置做决定！
func process(path []byte, index int, leftMinusRight int, leftRest int, ans *[]string) {
if index == len(path) {
*ans = append(*ans, string(path))
} else {
// index ( )
if leftRest > 0 {
path[index] = '('
process(path, index 1, leftMinusRight 1, leftRest-1, ans)
}
if leftMinusRight > 0 {
path[index] = ')'
process(path, index 1, leftMinusRight-1, leftRest, ans)
}
}
}
// 不剪枝的做法
func generateParenthesis2(n int) []string {
path := make([]byte, n<<1)
ans := make([]string, 0)
process2(path, 0, &ans)
return ans
}
func process2(path []byte, index int, ans *[]string) {
if index == len(path) {
if isValid(path) {
*ans = append(*ans, string(path))
}
} else {
path[index] = '('
process2(path, index 1, ans)
path[index] = ')'
process2(path, index 1, ans)
}
}
func isValid(path []byte) bool {
count := 0
for _, cha := range path {
if cha == '(' {
count
} else {
count--
}
if count < 0 {
return false
}
}
return count == 0
}执行结果如下：
图片左神java代码
