Generate Parentheses

PracticeNeetCode ↗LeetCode ↗

Given n pairs of parentheses, generate every combination of well-formed parentheses strings that can be made from them.

Example

Key Pointers

• A partial string stays "completable" into a valid one as long as you never place a ) when there's no unmatched ( to close.
• Track two counts — opens used, closes used — and only branch into placing ( while opens < n, and into ) while closes < opens.
• This is backtracking: build the string one character at a time, and invalid paths simply never get explored, so no filtering step is needed afterward.

Step-by-Step Analysis

1. Define a recursive function that takes the string built so far, the count of ( used, and the count of ) used.
2. Base case: once the string reaches length 2n, it's complete — add it to the results and return.
3. If opens < n, append (, recurse, then remove it (backtrack).
4. If closes < opens, append ), recurse, then remove it (backtrack).

Complexity

Time: O(4ⁿ / √n) — bounded by the nth Catalan number — Space: O(n) recursion depth, excluding output

Code

def generateParenthesis(n: int) -> list[str]:
    result = []

    def backtrack(current: list[str], open_count: int, close_count: int) -> None:
        if len(current) == 2 * n:
            result.append("".join(current))
            return
        if open_count < n:
            current.append("(")
            backtrack(current, open_count + 1, close_count)
            current.pop()
        if close_count < open_count:
            current.append(")")
            backtrack(current, open_count, close_count + 1)
            current.pop()

    backtrack([], 0, 0)
    return result

Code Explanation

How the solution above works, piece by piece.

1. backtrack builds the string one character at a time, tracking how many ( and ) it has used.
2. When the string has 2 * n characters it is complete and valid: save it.
3. Add ( if fewer than n have been used.
4. Add ) only if close_count < open_count, i.e. there is an open bracket to close. This rule alone guarantees validity.
5. current.pop() after each recursive call undoes the choice so the same list can be reused for the next branch. The number of results is the n-th Catalan number (5 for n = 3).

Visual Walkthrough

The full backtracking tree for n = 3:

Video Explanation

NeetCode — Stack, LeetCode 22