Generate Parentheses

Generate Parentheses is backtracking with fixed slots. There are 2n positions and each one gets ( or ). The trick is knowing, at every position, which of the two is still allowed — and the answer is two simple counting rules.

It is a favourite because the brute force is so easy to write and so clearly wasteful, and the fix is a clean example of pruning by a rule.

The problem

Given n, return every string of n opening and n closing brackets that is balanced — every ) closes an earlier unmatched (. Any order.

• n = 3 → ["((()))", "(()())", "(())()", "()(())", "()()()"]. Five balanced strings.
• n = 1 → ["()"].

Constraints: 1 ≤ n ≤ 8.

Clarifying questions

• Only round brackets? Yes.
• Any order? Yes.
• n = 0? Outside the constraints; the natural answer is [""].

Approach 1: the simple way — build every string, then check

Every position is ( or ), so there are 2^(2n) strings of length 2n. Build all of them and keep the balanced ones. A string is balanced if a running count (+1 for (, −1 for )) never goes below zero and ends at zero.

1import itertools23def is_valid(s: str) -> bool:4    depth = 05    for ch in s:6        depth += 1 if ch == "(" else -17        if depth < 0:8            return False                  # a ')' with nothing to close9    return depth == 01011def generate_parentheses_brute(n: int) -> list[str]:12    """Build all 2**(2n) strings, keep the balanced ones."""13    return ["".join(p) for p in itertools.product("()", repeat=2 * n)14            if is_valid("".join(p))]

Complexity: 4ⁿ strings, each checked in O(n): O(n × 4ⁿ).

Why it is too slow. For n = 8 it builds 65,536 strings to keep 1,430. For n = 10 it builds 1,048,576 to keep 16,796. Half the strings start with ), which is dead from the first character, and the code still fills in the other 2n − 1 positions before rejecting it.

The key insight

Look at a prefix and ask: can it still become balanced? It can, exactly when both of these hold:

1. It has used at most n opening brackets. More than n and there are too many to close.
2. It has closed no more than it has opened. The moment ) outnumbers (, some ) has nothing to close.

So at each position:

• You may add ( if opened < n.
• You may add ) if closed < opened.

Follow those two rules and every prefix you build can be finished, so every full string you reach is valid. Nothing is built and thrown away. Two counters are the whole state; you never need to re-scan the string.

Why are the two rules enough? Take any prefix that obeys them, say (()( for n = 3: opened = 3, closed = 1. Finish it by adding the missing n - opened opening brackets (none here) and then n - closed closing brackets: (()()). The running count never drops below zero, because closed never passes opened, and it ends at zero, because both counts reach n. So any prefix that obeys the rules has at least one balanced ending, and a prefix that breaks either rule has none. The rules are exactly the test "is this prefix still alive?".

This is also why the rules are checked before adding a character, not after. A check after the fact would build ) at the front, notice it is dead, and throw it away. A check before never builds it.

Approach 2: backtracking with two counters

1def generate_parentheses(n: int) -> list[str]:2    """Every balanced string of n pairs, never building an invalid prefix."""3    result: list[str] = []4    path: list[str] = []56    def backtrack(opened: int, closed: int) -> None:7        if len(path) == 2 * n:8            result.append("".join(path))    # join makes the copy9            return10        if opened < n:                      # an opening bracket is still available11            path.append("(")12            backtrack(opened + 1, closed)13            path.pop()14        if closed < opened:                 # a ')' has an unmatched '(' to close15            path.append(")")16            backtrack(opened, closed + 1)17            path.pop()1819    backtrack(0, 0)20    return result

There is no loop here — just two if blocks, one per possible character. Each block is its own choose–explore–undo. The path is a list of characters so that append and pop are O(1); "".join(path) builds the recorded string, which is the copy.

Dry run for n = 2, one row per call:

Eight calls, two answers, no dead ends. For n = 3 the same code makes 22 calls for 5 answers; for n = 8, 6,917 calls for 1,430 answers, against 65,536 full strings for the brute force.

Complexity. The number of balanced strings is the n-th Catalan number, C(2n, n) / (n + 1): 1, 2, 5, 14, 42, … It grows like 4ⁿ / (n × √n). Every node of the tree is a prefix of some answer, so the tree has at most 2n + 1 nodes per answer, and each answer costs O(n) to join. That gives O(n × Catalan(n)) time, usually written O(4ⁿ / √n). Working space is O(n) for the path and stack; the output is O(n × Catalan(n)).

Edge cases

• n = 1 — one call adds (, the next adds ), one answer.
• The first character — closed < opened is false at the start, so ) is never tried first. No special case needed.
• n at its limit — n = 8 gives 1,430 answers; the tree is tiny.

Follow-ups

• Just count them — no need to list: the answer is the Catalan number C(2n, n) / (n + 1), or a small dynamic programming table.
• Three kinds of bracket — the counters no longer suffice; keep a stack of open brackets and only allow the closing bracket that matches the top.
• Remove the fewest brackets to make a string valid — a harder cousin: count the extra ( and ) first, then backtrack over which ones to delete, pruning when the removals run out.