用asp.net做的网站模板,订餐网站开发方案,html5 网站模板下载,wordpress采集英文题目描述
数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。
示例 1#xff1a;
输入#xff1a; n 3 输出#xff1a; [“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2#xff1a;…题目描述
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入 n 3 输出 [“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2
输入 n 1 输出 [“()”]
提示
1 n 8
代码及注释
func generateParenthesis(n int) []string {// 初始化结果数组res : make([]string, 0)// 定义DFS函数var dfs func(left, right int, path string)dfs func(left, right int, path string) {// 如果左右括号都已使用完毕则将路径添加到结果数组中if left 0 right 0 {res append(res, path)return }// 如果左括号还有剩余则可以添加左括号if left 0 {dfs(left - 1, right, path ()}// 如果右括号的数量大于左括号则可以添加右括号if right left {dfs(left, right - 1, path ))}}// 调用DFS函数并初始化左右括号的数量dfs(n, n, )// 返回结果数组return res
}
代码解释 初始化结果数组 res : make([]string, 0)使用 make 函数初始化一个空的字符串数组 res用于存储生成的括号组合。 定义DFS函数 var dfs func(left, right int, path string)定义一个DFS函数 dfs该函数将用于生成所有有效的括号组合。 DFS函数的实现 dfs func(left, right int, path string) {// 如果左右括号都已使用完毕则将路径添加到结果数组中if left 0 right 0 {res append(res, path)return }// 如果左括号还有剩余则可以添加左括号if left 0 {dfs(left - 1, right, path ()}// 如果右括号的数量大于左括号则可以添加右括号if right left {dfs(left, right - 1, path ))}
}终止条件如果左右括号都已使用完毕即 left 0 right 0则将当前路径 path 添加到结果数组 res 中。添加左括号如果左括号 left 的数量还有剩余即 left 0则可以在当前路径 path 的末尾添加一个左括号并继续递归。添加右括号如果右括号 right 的数量大于左括号 left 的数量即 right left则可以在当前路径 path 的末尾添加一个右括号并继续递归。 调用DFS函数并初始化左右括号的数量 dfs(n, n, )调用DFS函数同时初始化左右括号的数量为 n。 返回结果数组 return res返回生成的所有有效的括号组合。
通过这样的DFS递归实现可以在 O(2^n) 的时间复杂度内生成所有有效的括号组合。
