Generate Parentheses
franklinqin0 StringDFSBacktracking
# Solution
Complexity is bounded by the n
-th Catalan number .
Complexity
time:
space: (due to implicit stack space)
# Backtracking
def generateParenthesis(self, n: int) -> List[str]:
res = []
def dfs(l, r, path):
# exit when running out of left/right parentheses
if l == 0 and r == 0:
res.append(path)
return
# error if # of ')' more than # of '('
if r < l:
return
# use a left parenthesis
if l > 0:
dfs(l - 1, r, path + '(')
# use a right parenthesis
if r > 0:
dfs(l, r - 1, path + ')')
dfs(n, n, '')
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Closure Number
Consider the closure number of a valid parentheses sequence S
: the least index >= 0
so that S[0]
, S[1]
, , S[2*index+1]
is valid. Clearly, every parentheses sequence has a unique closure number. We can try to enumerate them individually.
Algorithm: For each closure number c
, we know the starting and ending brackets must be at index 0
and 2*c + 1
. Then, the 2*c
elements between must be a valid sequence, plus the rest of the elements must be a valid sequence.
def generateParenthesis(self, n: int) -> List[str]:
if n == 0: return ['']
res = []
for i in range(n):
for left in self.generateParenthesis(i):
for right in self.generateParenthesis(n-1-i):
res.append('({}){}'.format(left, right))
return res
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8