题目
Given n
pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
1 <= n <= 8
思路
解法1:使用一个整数序列描述括号,一个整数表示有几个右括号加一个左括号,例如:0: ( 1: )( 2: ))(
,以此类推。那么根据1、2、3时的输出找规律:
1:0 ()
2:00 01 (()) ()()
3:000 001 002 010 011 ((())) (()()) (())() ()(()) ()()()
该过程类似于全排列,不过要求整数序列的总和要小于输入的值,不然就会出现()))((
这样无法闭合的情况。因此,针对该题可以先有限制的生成全排列的整数序列,然后再根据整数序列生成对应的括号。
解法2:dfs
代码
python版本:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def generate(nums):
cnt=0
res=''
for i in nums:
res+=i*')'+'('
cnt+=i
res+=(len(nums)-cnt)*')'
return res
res=[[0]]
for i in range(1,n):
res=[r+[j] for r in res for j in range(i+1-sum(r))]
res=[generate(r) for r in res]
return res
# dfs
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def dfs(now, l, r):
if l:
dfs(now+'(', l-1, r)
if l < r:
dfs(now+')', l, r-1)
if not (l or r):
res.append(now)
dfs('', n, n)
return res