题解 | #括号生成#递归回溯
括号生成
https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca
package main
import "fmt"
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return string字符串一维数组
*/
func generateParenthesis( n int ) []string {
// write code here
var res []string
// generate(n,n,[]byte{}, &res)
backtrack(n, n, "", &res)
fmt.Println(res)
return res
}
func generate(leftc, rightc int, path []byte, res *[]string){
if leftc==0 && rightc==0{
*res = append(*res, string(path))
return
}
if leftc == rightc {
path = append(path, '(')
generate(leftc-1, rightc, path, res)
path = path[:len(path)-1]
}
if leftc<rightc{
if leftc>0{
path = append(path, '(')
generate(leftc-1, rightc, path, res)
path = path[:len(path)-1]
}
path = append(path, ')')
generate(leftc, rightc-1, path, res)
path = path[:len(path)-1]
}
}
func backtrack(left, right int, str string, res *[]string){ //递归
if left==0 && right==0{
*res = append(*res, str)
return
}
// 使用新的字符串变量，所以无需回溯
if left>0{
backtrack(left-1, right, str+"(", res)
}
if left<right{
backtrack(left, right-1, str+")", res)
}
}
