算法 括号生成-(递归回溯+同向双指针)

牛客网: BM60

N对括号的所有合法组合

解题思路:

使用双指针进行递归回溯获取所有可能组合，left指代"("，right指代")"，均从0开始，left先行，left > right时，添加")"合法，right可前进，当left与right均递增到n时，获取一个有效组合。边界条件使用if判断。

代码:

// go
 
package main
// import "fmt"
 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return string字符串一维数组
*/
 
var res = []string{}
 
func process(left, right, n int, tmp string) {
    if left == n && right == n {
        res = append(res, tmp)
        return
    }
    if left < n {
        process(left+1, right, n, tmp+"(")
    }
    if right < n && left > right {
        process(left, right+1, n, tmp+")")
    }
}
 
func generateParenthesis( n int ) []string {
    // write code here
    if n == 0 {
        return []string{}
    }
    left := 0
    right := 0
    tmp := ""
    process(left, right, n, tmp)
    return res
}