题解 | #括号生成#递归回溯

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)
    }
}