leetcode_22

leetcode22


使用回溯法

首先确定三个关键问题

  1. Our Choice
    每次可以增加一个( or )
  2. constraints
    ) 必须在(之后 也就是)的数量必须小于(
  3. goal
    生成2*n个括号的字符串

推导过程如图所示

代码如下:

1
2
3
4
5
6
7
8
9
10
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
answer = []
def generate(left,right,now_parenthesis):
if left: generate(left-1,right,now_parenthesis+'(')
if right>left: generate(left,right-1,now_parenthesis+')')
if right ==0:
answer.append(now_parenthesis)
generate(n,n,'')
return answer