22. Generate Parentheses

String
Dynamic Programming
Backtracking

TIME

O(C(n) * n) where C(n) is the nth Catalan number

SPACE

O(n) excluding the output

Intuition

Generating all 2^(2n) strings and filtering the valid ones wastes almost all of the work. Instead build the string one character at a time and only ever place a character that keeps it extendable to a valid string. Two counters are enough: how many ( have been placed and how many ).

A ( is legal whenever fewer than n have been used. A ) is legal whenever it has an unmatched ( to close, i.e. close < open. Those two conditions are exactly the invariant for a valid prefix, so every leaf of the recursion is a complete well-formed string and nothing is ever discarded.

Approach

Keep a mutable buffer and the counts open and close.
If the buffer length is 2n, record the joined string and return.
If open < n, append (, recurse, pop.
If close < open, append ), recurse, pop.

Trying ( before ) at each step produces the results in lexicographic order, since ( sorts before ).

Complexity

Time: O(C(n) * n) where C(n) is the nth Catalan number, one unit of work per output character, plus O(n) to materialise each string
Space: O(n) for the buffer and the recursion stack, excluding the output

C(8) = 1430, so the output stays small across the whole constraint range.

Edge Cases

n = 1 → ["()"], the only option
n = 8 → 1430 strings, the largest case; no risk of deep recursion since the depth is 2n = 16
The buffer must be popped after each recursive call, or branches leak characters into their siblings
Checking the length rather than close == n as the stop condition works equally; both are reached at the same time

Code

from typing import List


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        """
        22. Generate Parentheses
        Time: O(C(n) * n) where C(n) is the nth Catalan number
        Space: O(n) excluding the output
        """
        result = []
        buf = []

        def backtrack(open_count: int, close_count: int) -> None:
            if len(buf) == 2 * n:
                result.append("".join(buf))
                return
            # '(' first so the output comes out lexicographically sorted
            if open_count < n:
                buf.append("(")
                backtrack(open_count + 1, close_count)
                buf.pop()
            if close_count < open_count:
                buf.append(")")
                backtrack(open_count, close_count + 1)
                buf.pop()

        backtrack(0, 0)
        return result

import java.util.ArrayList;
import java.util.List;

/**
 * 22. Generate Parentheses
 * Time: O(C(n) * n) where C(n) is the nth Catalan number
 * Space: O(n) excluding the output
 */
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(new StringBuilder(), 0, 0, n, result);
        return result;
    }

    private void backtrack(StringBuilder buf, int open, int close, int n, List<String> result) {
        if (buf.length() == 2 * n) {
            result.add(buf.toString());
            return;
        }
        // '(' first so the output comes out lexicographically sorted
        if (open < n) {
            buf.append('(');
            backtrack(buf, open + 1, close, n, result);
            buf.deleteCharAt(buf.length() - 1);
        }
        if (close < open) {
            buf.append(')');
            backtrack(buf, open, close + 1, n, result);
            buf.deleteCharAt(buf.length() - 1);
        }
    }
}