# Generate Parentheses

StringDFSBacktracking

## # Solution

Complexity is bounded by the n-th Catalan number $\frac{1}{n+1} \binom{2n}{n} \le \frac{4^n}{\sqrt{n}}$.

Complexity

time: $O(\frac{4^n}{\sqrt{n}})$
space: $O(\frac{4^n}{\sqrt{n}})$ (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

### # Closure Number

Consider the closure number of a valid parentheses sequence S: the least index >= 0 so that S[0], S[1], $\cdots$, 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