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

牛客网: 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 }