Generate Parentheses

Problem

Given n, return all combinations of n pairs of parentheses that are well formed, meaning every opening bracket is closed in the right order.

Approach

Build the string one character at a time with backtracking, tracking how many opening and closing brackets have been placed.

An opening bracket can be added while fewer than n have been used. A closing bracket can be added only while there are more opening brackets than closing ones, which is exactly the rule that keeps the prefix valid.

Because invalid prefixes are never built, every finished string of length 2n is a valid answer.

Solution

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        result = []
        path = []

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

        backtrack(0, 0)
        return result

Complexity

• Time: O(4^n / √n), the growth rate of the Catalan numbers that count the valid strings.
• Space: O(n) for the recursion and the current string, excluding the output.

Edge cases

• n = 1 returns a single pair.
• The output size grows very quickly, so n stays small in practice.