Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Given n pairs of parentheses, generate every string that is:

  • exactly 2n characters long
  • made only of ( and )
  • balanced at every point

The last condition is the important one.

A valid parentheses string never has more closing parentheses than opening parentheses in any prefix.

So this is not really a “try every string and filter later” problem. It is a “build only prefixes that can still become valid” problem.

The key insight

At any point while building the string, only two counts matter:

  • how many opening parentheses have been used
  • how many closing parentheses have been used

From there, the rules are simple:

  • an opening parenthesis can be added if open_used < n
  • a closing parenthesis can be added if close_used < open_used

That second rule is the whole trick.

It guarantees the partial string is never invalid, because it prevents a prefix like ")" or "())" from ever being created.

This means the search tree gets pruned very aggressively. The algorithm explores only states that can still lead to a legal answer.

How to derive the optimal approach

The natural first idea is brute force:

  1. Generate all 2^(2n) strings of length 2n.
  2. Check which ones are balanced.

That is far too expensive, because most of those strings are obviously impossible.

The better way is to think in terms of prefixes:

  • If ( is still available, it is always safe to place it.
  • If ) would make closes exceed opens, it can never lead to a valid answer, so skip it immediately.

Once the problem is framed that way, backtracking becomes the natural solution:

  • make a choice
  • keep going only if the prefix is still legal
  • record the string when it reaches length 2n

This is asymptotically optimal for generating the full answer set, because any correct algorithm must spend time writing out every valid string anyway.

Two useful ways to think about it

  • Backtracking with pruning: the practical interview answer. It is easy to reason about and generates only valid prefixes.
  • Dynamic programming by composition: for each split of n - 1 pairs, build strings of the form "(" + left + ")" + right. This is mathematically elegant, but usually less direct to implement and explain.

For production or interview use, backtracking is the cleanest answer.

Complexity

Let C_n be the nth Catalan number, which is the number of valid parentheses strings with n pairs.

  • Time: O(C_n * n) because there are C_n outputs and each completed string has length 2n
  • Extra space: O(n) for the recursion stack and the current path, excluding the returned output
  • Output space: O(C_n * n)

Python solution

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        return self._build_valid_parentheses(pair_count=n)

    def _build_valid_parentheses(self, pair_count: int) -> list[str]:
        combinations: list[str] = []
        current_characters: list[str] = []

        self._search(
            pair_count=pair_count,
            open_used=0,
            close_used=0,
            current_characters=current_characters,
            combinations=combinations,
        )

        return combinations

    def _search(
        self,
        pair_count: int,
        open_used: int,
        close_used: int,
        current_characters: list[str],
        combinations: list[str],
    ) -> None:
        if len(current_characters) == pair_count * 2:
            combinations.append("".join(current_characters))
            return

        if open_used < pair_count:
            current_characters.append("(")
            self._search(
                pair_count=pair_count,
                open_used=open_used + 1,
                close_used=close_used,
                current_characters=current_characters,
                combinations=combinations,
            )
            current_characters.pop()

        # A closing parenthesis is safe only when there is an unmatched "(".
        if close_used < open_used:
            current_characters.append(")")
            self._search(
                pair_count=pair_count,
                open_used=open_used,
                close_used=close_used + 1,
                current_characters=current_characters,
                combinations=combinations,
            )
            current_characters.pop()

Why this implementation is solid

  • It keeps the state minimal: only the counts and the current character buffer.
  • It never builds invalid prefixes, so there is no expensive validation pass afterward.
  • It uses a mutable character list during recursion and joins only when a full answer is ready, which avoids unnecessary intermediate string creation.

The core idea to remember is simple: valid parentheses strings are defined by prefix constraints, so the best solution builds them one legal prefix at a time.