首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python|回溯算法解括号生成问题

Python|回溯算法解括号生成问题

作者头像
算法与编程之美
发布2020-04-20 13:10:38
7450
发布2020-04-20 13:10:38
举报

问题描述

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

示例:

输入:n = 3

输出:[

"((()))",

"(()())",

"(())()",

"()(())",

"()()()"

]

解决方案

这道题的第一思路是用全排列把所有的括号可能排出来,再用栈的思路来检测是否为有效括号组。然后去百度了下全排列的算法代码,要用到回溯,而且代码很长。既然全排要用回溯,还不如直接用回溯算了。然后就发现,这个括号很像二叉树。

图2.1思路分析二叉树示意

简单的画了下。众所周知树和回溯可是老伙伴了。代码实现的主要突破是括号的插入方法和向下搜索的条件。借用栈的思路可以知道插入‘)’时必须有‘(’而且‘(’的数量必须比‘)’的数量多有了这一点就可以开始代码了。

python代码:

class Solution: def generateParenthesis(self, n): res = [] self.dfs(res, n, n, '') return res def dfs(self, res, left, right, path): #遍历深度达到n及左右括号都用完了时返回path路径 if left==right==0: res.append(path) return #插入右括号的时机 if left<right: self.dfs(res,left,right-1,path+')') #插入左括号的时机 if left>0: self.dfs(res,left-1,right,path+'(') x=Solution() print(x.generateParenthesis(n=3))

结语

回溯法主要可以用在三种问题上(前题是需要穷举):

1 .判断有没有解

2.求所有解的数量或具体信息

3.求最优解

这道题就属于第二种。

回溯法的基本套路是使用两个变量: res 和 path,res 表示最终的结果,path 保存已经走过的路径。如果搜到一个状态满足题目要求,就把 path 放到 res 中。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-04-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法与编程之美 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档