Generate Parentheses

Generate only prefixes that can still become valid. The balance state tells you exactly which branches to keep.

Start with the output contract

Given n pairs of parentheses, generate every distinct well-formed string using exactly:

• n opening parentheses: '('
• n closing parentheses: ')'

The input constraint is 1 <= n <= 8. Every output therefore has length 2n.

A sequence is well-formed when, while reading from left to right:

1. The number of closing parentheses never exceeds the number of opening parentheses.
2. The final number of opening and closing parentheses is equal.

For n = 3, the five valid outputs are:

((()))
(()())
(())()
()(())
()()()

The order is usually irrelevant. The required result is the complete set of valid combinations.

That definition gives us a more useful construction rule:

Build a prefix only when it can still be extended into a complete valid sequence.

This is the key shift. We do not need to generate arbitrary strings and repair them later. We can prevent invalid prefixes from entering the search tree.

Why blind permutation wastes the search

The tempting baseline is to make two choices at every position: add '(' or add ')'. Since the final string has 2n positions, this explores every binary string of that length. Only afterward do we check whether each completed string is valid.

That approach spends most of its work below prefixes that were already impossible.

For example, once a prefix becomes:

())

it cannot be repaired by adding more characters. The third character closes more groups than have been opened. Every descendant of that prefix is dead, but blind generation still explores those descendants until the string reaches length 2n.

Backtracking gives us a way to cut off that entire subtree:

1. Choose a character.
2. Add it to the current path.
3. Recurse only if the new state remains legal.
4. Remove the character before trying the next choice.

The pruning rule is the real algorithm. Recursion is just the machinery that walks the remaining tree.

Derive the two-counter state

The current path tells us what has been built. We also need to know what choices remain legal.

Track two counters:

• open_used: opening parentheses already placed
• close_used: closing parentheses already placed

The mutable path stores the current partial string.

Each counter answers a different obligation:

State	Meaning	Legal action
open_used < n	Opening parentheses remain	Add '('
close_used < open_used	At least one opening parenthesis is unmatched	Add ')'
open_used == n and close_used == n	The path is complete	Record it

The opening rule is straightforward. We cannot use more than n opening parentheses:

if open_used < n:
    # '(' is legal

The closing rule carries the important reasoning:

if close_used < open_used:
    # ')' is legal

Why must close_used be less than open_used?

Define the current balance as:

balance = open_used - close_used

A close consumes one unmatched open. If balance == 0, there is nothing available to close. Adding ')' would make the new balance negative, so the prefix would already be invalid.

Therefore, before placing a close:

balance > 0

which is exactly equivalent to:

open_used > close_used

The two counters are sufficient because they encode both parts of the problem:

• how many symbols of each type remain
• whether the current prefix has an unmatched opening parenthesis

There is no need to rescan the path to recompute the balance.

Prove the pruning rule

A correct backtracking solution needs more than a plausible condition. State the invariant explicitly.

Recursive invariant: Every path that reaches backtrack(open_used, close_used) has never had more closing parentheses than opening parentheses, and both counters are between 0 and n.

Now check each transition.

Adding an opening parenthesis

The opening branch is allowed only when:

open_used < n

So the new opening count remains within the available limit. Adding an opening increases the balance by one, so it cannot violate the rule that balance must remain nonnegative.

The invariant is preserved.

Adding a closing parenthesis

The closing branch is allowed only when:

close_used < open_used

Before the close, the balance is positive. Adding ')' reduces the balance by one, but the result is still nonnegative.

The invariant is preserved again.

Completeness

Could the algorithm accidentally prune a valid sequence?

Consider the next character in any valid sequence:

• If it is '(', then fewer than n openings have been used, so the opening branch is allowed.
• If it is ')', validity guarantees that the prefix before it has more openings than closings, so the closing branch is allowed.

Thus every character choice made by a valid sequence remains available. No valid sequence is pruned.

Soundness

A path is recorded only when:

open_used == n and close_used == n

So it contains exactly n openings and n closings. The invariant guarantees that no prefix had more closes than opens. Therefore, every recorded path is well-formed.

The proof is reusable in interviews:

1. Name the legal state.
2. Show that every legal transition preserves it.
3. Show that every valid solution uses only legal transitions.
4. Record only complete states.

That is stronger than saying “the recursion tries all possibilities.”

Dry-run n = 3 and watch the tree shrink

At the root:

path = ""
open_used = 0
close_used = 0
balance = 0

Only '(' is legal. A close would make the balance negative.

Here are several representative states:

Path	open_used	close_used	Balance	Legal next moves
""	0	0	0	'('
"("	1	0	1	'(', ')'
"()"	1	1	0	'('
"(("	2	0	2	'(', ')'
"(()"	2	1	1	'(', ')'

Walk one complete branch:

"" 
"("
"(("
"((("
"((())"
"((()))"

At "((()))", both counters equal 3, so the result is recorded.

Now take another branch:

""
"("
"(("
"(()"
"(()("
"(()()"
"(()())"

The algorithm explores both choices whenever both are legal. But it refuses to create the invalid prefix "())":

"()"    -> open_used = 1, close_used = 1, balance = 0
"())"   -> illegal

The close is rejected immediately. We do not create "())", and we do not explore any strings beneath it. That is the pruning benefit in visible form: the tree loses an entire dead branch at the moment its invariant fails.

With the usual “try '(' first” implementation, the results often appear in the order shown earlier. That ordering is an implementation consequence, not part of the contract.

Implement the backtracking solution in Python

Use a list for path because the recursion mutates it in place. Appending and popping expose the search tree directly.

from typing import List


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

        def backtrack(open_used: int, close_used: int) -> None:
            # A complete path uses exactly n pairs.
            if open_used == n and close_used == n:
                results.append("".join(path))
                return

            # We can still spend an opening parenthesis.
            if open_used < n:
                path.append("(")
                backtrack(open_used + 1, close_used)
                path.pop()

            # A close is legal only when an unmatched open exists.
            if close_used < open_used:
                path.append(")")
                backtrack(open_used, close_used + 1)
                path.pop()

        backtrack(0, 0)
        return results

Each piece of state has one job:

• results stores complete answers.
• path stores the current prefix.
• open_used enforces the total number of opening parentheses.
• close_used enforces both the total number of closing parentheses and the balance rule.

The pop() calls are not cosmetic cleanup. They restore the state before the recursive call so the next sibling branch starts from the correct prefix.

Suppose the path is "(()" and the algorithm tries adding '('. After that branch returns, the path must become "(()" again before trying ')'. Without the pop, the sibling branch inherits the previous choice. The recursion then stops representing independent paths and starts leaking state between them.

This is the backtracking rhythm:

append
recurse
pop

Keep that rhythm visible in an interview. Hidden mutation is where many otherwise correct recursive solutions break.

A second common mistake is to validate only at length 2n. That produces the right answer set only if the implementation also checks every completed candidate, but it throws away the main advantage of backtracking: invalid prefixes should be rejected before their descendants are built.

Complexity, edge cases, and the interview check

The number of valid strings is the nth Catalan number, usually written as C_n. Because the algorithm must return every string, the output itself is already combinatorial.

Each returned string has length 2n, so writing the complete result set costs:

O(C_n * n)

up to a constant factor for the two-character-pair length. The traversal also visits legal prefixes, but the important practical characterization is output-sensitive: the work must at least account for every character in every returned string.

Space has two separate parts:

• Auxiliary recursion stack and mutable path: O(n)
• Returned results: O(C_n * n)

When interviewers ask for space complexity, say which one you mean. The algorithm uses O(n) auxiliary space, excluding the required output collection. Including the returned results, storage is proportional to the total output size.

Useful checks:

• n = 1 returns ["()"].
• The root must never allow ')'.
• Every result must have length 2n.
• Every result must contain exactly n opening and n closing parentheses.
• No path may ever have close_used > open_used.
• Both append operations must have matching pop operations.
• The terminal condition should be based on both counters reaching n.

The supplied constraint begins at n = 1, so the implementation does not need to define behavior for negative inputs or unsupported values.

The recognition rule

When a generation problem has a prefix constraint that can be represented with small state, do not generate everything and filter afterward.

Track the resource counts. Identify the prefix invariant. Generate only legal prefixes.

For this problem:

• open_used < n means an opening parenthesis is available.
• close_used < open_used means the balance is positive, so a close is safe.
• open_used == close_used == n means the sequence is complete.

In a new interview problem, ask the same question before writing recursion:

What must be true about the current prefix, and what small piece of state proves it?

Then build the tree around that answer. Clear the noise. Keep the legal branches. Let the invariant do the pruning.