Description
Return every well-formed string containing n pairs of parentheses. Each prefix must have at least as many opening parentheses as closing ones; assume n >= 1.
Solution
def generate_parenthesis(n):
result = []
def build(text, opened, closed):
if len(text) == 2 * n:
result.append(text)
return
if opened < n:
build(text + "(", opened + 1, closed)
if closed < opened:
build(text + ")", opened, closed + 1)
build("", 0, 0)
return resultExamples
Example 1
- Input
[1]- Output
["()"]
Only one arrangement is valid.
Example 2
- Input
[2]- Output
["(())","()()"]
The pairs may nest or sit side by side.
Example 3
- Input
[3]- Output
["((()))","(()())","(())()","()(())","()()()"]
These are the five valid arrangements.
Approach
Build strings by backtracking. Add an opening parenthesis while fewer than n have been used, and a closing one only when there is an unmatched opening. Emit a string once its length reaches 2n.
Time & space
O(n C_n) time and O(n^2) auxiliary space for retained prefix strings in Python and Java (O(n) in Go), excluding output; C_n is the nth Catalan number and n is the pair count.