括号生成题目来源：https://leetcode-cn.com/problems/generate-parentheses/submissions/题目给n表示生成括号的对数，请写一个函数让它可以生成所有可能和有效的括号组合。例如，给定n=3，生成的结果是：["((()))","(()())","(())()","()(())",《()()()》]解题思路：回溯算法+剪枝；按照上面的思路做减法，示意图如下，假设n=2：从上图可以得出：当左右括号的可用个数大于0时，一个分支可以生成；尝试在左侧生成分支时，只需要确认可用的左括号个数是否大于0；当尝试在右侧生成分支时，需要考虑左括号的可用数量。这里只有当可用的左括号个数小于可用的右括号个数时，分支才能正常生成，否则需要剪枝；当可用的左右括号个数等于0时，表示结束。代码实现类Solution:defgenerateParenthesis(self,n:int)->List[str]:res=[]cur_chr=''defdfs(cur_chr,left,right):'''深度优化遍历Args:cur_chr:current递归得到的结果left：可以使用的左括号个数right：可以使用的右括号个数returns：返回所有可能的结果集'''#当左右括号个数为0时，添加放到结果集中返回ifleft==0andright==0:res.append(cur_chr)return#如果左括号可用个数大于右括号，不满足设置，直接返回ifleft>right:return#左括号可用个数大于0，添加左括号ifleft>0:dfs(cur_chr+'(',left-1,right)#右括号可用个数大于0,ifright>0加右括号:dfs(cur_chr+')',left,right-1)dfs(cur_chr,n,n)returnres执行结果以上是主要的关于使用回溯算法+剪枝解决《括号生成》问题的内容。欢迎关注微信公众号《书所集录》
