做微信电影网站,邢台网站建设,温江区网站建设,网站设计模板含数据库文章目录 题目链接解题思路解题代码 题目链接
22. 括号生成
数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。
示例 1#xff1a; 输入#xff1a;n 3 输出#xff1a;[“((()))”,“(()())”,“(())()… 文章目录 题目链接解题思路解题代码 题目链接
22. 括号生成
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1 输入n 3 输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2 输入n 1 输出[“()”]
解题思路
下面我们根据回溯算法三步走写出对应的回溯算法。
明确所有选择括号组合中的每个位置都可以从 ( 或者 ) 中选出。并且只有在 symbol n 的时候才能选择 (在 symbol 0 的时候才能选择 )。 明确终止条件当遍历到决策树的叶子节点时就终止了。即当前路径搜索到末尾时递归终止。 将决策树和终止条件翻译成代码
定义回溯函数 backtracking(symbol, index): 函数的传入参数是 symbol用于表示是否当前组合是否成对匹配index当前元素下标全局变量是 parentheses用于保存所有有效的括号组合parenthesis当前括号组合。backtracking(symbol, index) 函数代表的含义是递归根据 symbol在 ( 和 ) 中选择第 index 个元素。 书写回溯函数主体给出选择元素、递归搜索、撤销选择部分。 从当前正在考虑元素到第 2 * n 个元素为止枚举出所有可选的元素。对于每一个可选元素 约束条件symbol n 或者 symbol 0。选择元素将其添加到当前括号组合 parenthesis 中。递归搜索在选择该元素的情况下继续递归选择剩下元素。撤销选择将该元素从当前括号组合 parenthesis 中移除。
if symbol n:parenthesis.append(()backtrack(symbol 1, index 1)parenthesis.pop()
if symbol 0:parenthesis.append())backtrack(symbol - 1, index 1)parenthesis.pop()明确递归终止条件给出递归终止条件以及递归终止时的处理方法。 当遍历到决策树的叶子节点时就终止了。也就是当 index 2 * n 时递归停止。并且在 symbol 0 时当前组合才是有效的此时将其加入到最终答案数组中。
解题代码
class Solution:def generateParenthesis(self, n: int) - List[str]:parentheses []parenthesis []def backtrack(symbol, index):if n * 2 index:if symbol 0:parentheses.append(.join(parenthesis))else:if symbol n:parenthesis.append(()backtrack(symbol 1, index 1)parenthesis.pop()if symbol 0:parenthesis.append())backtrack(symbol - 1, index 1)parenthesis.pop()backtrack(0, 0)return parentheses参考资料datawhalechina
