• ## Projects

Back to the posts

## Generate parentheses

Given n, write a function to generate all combinations of well-formed parentheses. This problem can be solved in LeetCode.

## Examples

n = 1
["()"]

n = 2
["(())", "()()"]

n = 3
["((()))", "(()())", "(())()", "()(())", "()()()"]

## Solution

If the problem is to find the number of the combination, this is a Catalan number sequence problem. However, we need to print all combinations. Therefore, this is a typical backtracking search problem because we need to explore every possible outcomes.

Let's look at the code first.

from typing import List

def generate_parenthesis(n: int) -> List[str]:
"""Generate all combinations of well-formed parentheses

Example:
>>> generate_parenthesis(3)
['((()))', '(()())', '(())()', '()(())', '()()()']
"""

def backtrack(current: str,
left: int,
right: int,
result: List[str] = []) -> List[str]:

if len(current) == 2 * n:
result.append(current)

if left < n:
backtrack(current + "(", left + 1, right)

if right < left:
backtrack(current + ")", left, right + 1)

return result

return backtrack("", 0, 0)

One way of tackling this problem is to track the number of open(left) parentheses and the number of close(right) parentheses.

Suppose

• left: the number of open parentheses
• right: the number of close parentheses

Then,

• We know we can have n open parentheses and n close parentheses
• Therefore, add a open parenthesis as long as left < n.
• We can only add a closing parenthesis when right < left.

Notice that we don't break the validity of the parentheses as long as we close parentheses when right < left.

© 2021 Mo Kweon. All rights reserved.