leetcode22 括号生成-组合型回溯

题目

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

示例

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

解析

func generateParenthesis(n int) []string {m := 2 * nans := []string{}var path []bytevar dfs func(i, left int)dfs = func(i, left int) {if i == m {ans = append(ans, string(path))}if left < n {path = append(path, '(')dfs(i+1, left+1)path = path[:len(path)-1]}if i-left < left {path = append(path, ')')dfs(i+1, left)path = path[:len(path)-1]}}dfs(0, 0)return ans
}

这道题有如下细节需要注意，首先是n代表括号的对数，那么就需要乘以2来计算出左括号+右括号数量之和；在dfs逻辑中，如果左括号的数量小于n，则代表还有可以存左括号的位置；i-left其实就是右括号，右括号的数量小于left，表示还可以添加右括号