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 <= 8Source
def generate_parenthesis(n):
"""Recursive approach."""
def dfs(left, right, string):
nonlocal result
if not left: # if we can't open a new partenthese
result.append(string + ')' * right) # we close all opened ones
elif left == right: # if we closed all opened parentheses, then
dfs(left-1, right, string + '(') # we can only open a new one
else:
dfs(left-1, right, string + '(') # we can choose to open a parenthese
dfs(left, right-1, string + ')') # or we can choose to close a parenthese
result = []
dfs(n, n, '')
return result
def generate_parenthesis(n):
"""Alternative version of first solution."""
def generate(left, right):
if not left:
return [ ')' * right]
if right == left:
return [ '(' + x for x in generate(left-1, right)]
return ([ '(' + x for x in generate(left-1, right)] + \
[ ')' + x for x in generate(left, right-1)])
return generate(n, n)
def generate_parenthesis(n):
"""Alternative version of first solution."""
def dfs(left, right, string):
nonlocal result
if left:
dfs(left-1, right, string + '(')
if right > left:
dfs(left, right-1, string + ')')
if not right:
result.append(string)
return result
result = []
return dfs(n, n, '')
def generate_parenthesis(n):
"""Alternative version of abvove solution using a generator."""
def generate(left, right, string):
if right >= left >= 0:
if not right:
yield string
for x in generate(left-1, right, string + '('):
yield x
for x in generate(left, right-1, string + ')'):
yield x
return list(generate(n, n, ''))
generate_parenthesis(3)
['((()))', '(()())', '(())()', '()(())', '()()()']
generate_parenthesis(1)
['()']
Solve it both recursively and iteratively.
def generate_parenthesis(n):
"""Using dynamic Programming
Generate 1x pair. For the (n-1) pairs left, we can:
- Generate 0x pair inside AND (n-1)x pair afterwards
- OR Generate 1x pair inside AND (n-2)x pair afterwards
- OR Generate 2x pair inside AND (n-3)x pair afterwards
- ...
- OR Generate (n-2)x pair inside AND 1x pair outside
- OR Generate (n-1)x pair inside AND 0x pair outside
f(1) = () = (f(0))
f(2) = ()(), (()) = (f(0))+f(1), (f(1))
f(3) = () ()(), () (()), (())(), ((())), (()())
\ / \ \ /
f(3) = (f(0)) + f(2), (f(1)) + f(1), (f(2))
f(n) = (f(0)) + f(n-1), (f(1)) + f(n-2), (f(2)) + f(n-3), ... (f(n-2)) + (f(0)), (f(n-1))
"""
dp = [ [] for _ in range(n+1)] # Don't use [ [] ] * N = list containing the same list object N times
dp[0].append('')
for i in range(1, n + 1):
for j in range(i):
dp[i] += [ '(' + x + ')' + y for x in dp[j] for y in dp[i-j-1]]
return dp[-1]