Generate Parentheses

Problem

https://leetcode.com/problems/generate-parentheses/

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 <= 8

Pattern

String, Dynamic Programming, Backtracking

Approaches

Backtracking

Explanation

Let’s construct a well-formed parentheses string of size 3 from left to right.

(, (), ()(, ()((, ()((), ()(())

Observe that

1. we can only add ‘)’ when the number of ‘(’ is \(>\) to the number of ‘)’

2. we can keep adding ‘(’ until we run out.

We can recursively add parenthesis according to these 2 rules until we exhaust the limit of left and right parentheses.

Code

def generateParenthesis(n: int) -> list[str]:
    """Generate all combinations of well-formed parentheses."""
    paren = []
    genParen(n, n, "", paren)
    return paren


def genParen(left: int, right: int, s: str, paren: list[str]):
    """Recursively add parenthesis to ``s``, finally appending ``s`` to
    ``paren``.
    """
    if left == 0 and right == 0:
        paren.append(s)
        return

    if right > left:
        genParen(left, right - 1, s + ")", paren)

    if left > 0:
        genParen(left - 1, right, s + "(", paren)

Test

>>> from generate_parentheses__backtracking import generateParenthesis
>>> paren = generateParenthesis(3)
>>> set(paren) == {'((()))', '(()())', '(())()', '()(())', '()()()'}
True
>>> generateParenthesis(1)
['()']

Complexity

Measure	Complexity	Notes
Time	\(O(4^n / \sqrt{n})\)	Catalan number of combinations
Auxiliary Space	\(O(n)\)	recursive call stack and string storage

generate_parentheses__backtracking.generateParenthesis(n: int) → list[str]

Generate all combinations of well-formed parentheses.

generate_parentheses__backtracking.genParen(left: int, right: int, s: str, paren: list[str])

Recursively add parenthesis to s, finally appending s to paren.