括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1 输出：["()"]

提示：

1 <= n <= 8

解题思路：

  1. 定义递归函数 generate(left, right, path, result):

    • left: 剩余左括号数量
    • right: 剩余右括号数量
    • path: 当前生成的括号字符串
    • result: 最终结果列表

  2. 结束条件:
    当 left 和 right 都为 0 时，说明生成了一个有效的括号组合，将其添加到 result 中。 递归步骤:

  3. 如果还有剩余左括号 (left > 0)，则添加一个左括号到 path，并递归调用 generate(left-1, right, path+"(", result)。

  4. 如果右括号数量大于左括号数量 (right > left)，则添加一个右括号到 path，并递归调用 generate(left, right-1, path+")", result)。

func generateParenthesis(n int) []string {

 	var result []string
 
 	var backtrack func(left, right int, path string, res *[]string)
 	backtrack = func(left, right int, path string, res *[]string) {
 		if left == 0 && right == 0 {
 			*res = append(*res, path)
 			return
 		}
 		// 左括号有剩余
 		if left > 0 {
 			backtrack(left-1, right, path+"(", res)
 		}
 
 		if right > left {
 			backtrack(left, right-1, path+")", res)
 		}
 	}
 	backtrack(n, n, "", &result)
 	return result
 }
 
 /*
 思路：回溯法
 */
 func generateParenthesis2(n int) []string {
 	var result []string
 	backtrack("", 0, 0, n, &result)
 	return result
 }
 
 func backtrack(path string, left, right, n int, result *[]string) {
 	// 终止条件，当path长度达2*n
 	if len(path) == 2*n {
 		*result = append(*result, path)
 		return
 	}
 
 	// 先放左括号
 	if left < n {
 		backtrack(path+"(", left+1, right, n, result)
 	}
 	if right < left {
 		backtrack(path+")", left, right+1, n, result)
 	}
}