LeetCode.22。括号生成
题目描述:
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组
输入输出实例:
思路:对于这道题目我们可以用回溯法,创建一个函数backtrack(当前字符,左括号数量,右括号数量),这个函数用来递归生成所有的括号组成可能。我们先前创立一个空列表,在backtrack递归过程中满足条件的我们放到列表中,最后返回列表。
在backtrack中,如果当前的字符组成满足长度等于2*n的时候,我们得到一个有效的括号组成,将其加到ans列表;如果当前左括号比n少,我们继续添加左括号;如果当前右括号比左括号少,我们添加右括号。
比如当n==2时候,我们先是添加一个左括号->再添加左括号->再添加右括号->再添加右括号->满足条件将‘(())'存入ans。然后返回到'('尝试添加右括号(即'()')->再添加左括号->再添加右括号->将’()()‘存入ans->递归结束,return ans
class Solution:def generateParenthesis(self, n: int) -> List[str]:#构建函数backtrack用来构建有效括号组合def backtrack(s:str,left:int,right:int):#达到目标长度放入if len(s) == 2*n:ans.append(s)return#左括号数量不够可加左括号if left < n :backtrack(s+'(',left+1,right)#右括号不足加右括号if right < left :backtrack(s+')',left,right+1)ans = []backtrack('',0,0)return ans