43.leetcode22_generate

43.leetcode22_generate_parentheses

1.题目描述

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

给定n对括号，编写一个函数来生成格式正确的括号的所有组合。

2.题目分析

采用递归调用的方法。相当于在括号数不足n之前，括号字符串都有添加"("和")"的两种可能。但是需要设定条件避免"()("这种情况

3.解题思路（43ms)

 1 class Solution(object):
 2     def generateParenthesis(self, n):
 3         """
 4         :type n: int
 5         :rtype: List[str]
 6         """
 7         result=[]
 8         self.parenthesis(n,n,"",result)
 9         return result
10     
11     def parenthesis(self,l,r,s,strs): #定义匹配括号的函数
12         if l==0 and r==0: #匹配完成向strs中添加新括号字符串
13             strs.append(s)
14         if l>0: #匹配左括号
15             self.parenthesis(l-1,r,s+'(',strs)
16         if r>l: #匹配右括号，r>l避免出现匹配错误
17             self.parenthesis(l,r-1,s+')',strs)