Generate Parentheses

35 min · generateParenthesis()

A closing parenthesis can't pay a debt that hasn't been opened yet. That one rule lets you reject bad strings long before they're finished.

For an integer n, build every string that uses exactly n opening parentheses and n closing parentheses in a valid arrangement. A string is valid when every opening parenthesis has a later closing partner and no prefix closes more pairs than it opens.

Return the valid strings in any order, with no duplicates.

Constraints

1 <= n <= 8
The largest case has 1,430 valid strings.

Hints

A truthful first draft

You can generate every length-2 × n string made from ( and ), then scan each one with a balance counter. How many candidates does that create?

Protect every prefix

Track how many opening and closing parentheses you've placed. You may add ( while the opening count is below n; when is adding ) safe?

Two gates

Add a closing parenthesis only when close < open. Once both counts reach n, the current path is a complete answer and needs no separate validity check.

Follow-up

Could you compute how many answers exist for a given n without constructing any of the strings?

Visible cases

Examples

Example 1

ready

Input: n = 1
Expected: [ "()" ]
Why: one pair has only one valid arrangement

Example 2

ready

Input: n = 3
Expected: [ "((()))", "(()())", "(())()", "()(())", "()()()" ]
Why: all five strings keep every prefix balanced

Example 3

ready

Input: n = 2
Expected: [ "(())", "()()" ]
Why: the pairs may nest or sit side by side

Interview signal

Asked at

AmazonGoogleMeta

Generate + filter

Start with all 2^(2 × n) = 4ⁿ strings of the right length. A balance counter rises for ( and falls for ). Reject a candidate if the balance ever goes negative, and keep it only if the final balance is zero.

from itertools import product
 
 
def generate_parenthesis(n: int) -> list[str]:
    result: list[str] = []
 
    for symbols in product("()", repeat=2 * n):
        balance = 0
        valid = True
        for symbol in symbols:
            balance += 1 if symbol == "(" else -1
            if balance < 0:
                valid = False
                break
        if valid and balance == 0:
            result.append("".join(symbols))
 
    return result

Each candidate may need a full scan. Time O(4ⁿ · n). Space O(n) auxiliary for one candidate, excluding the returned strings.

Valid-prefix backtracking

This is the backtracking pattern: extend one candidate, explore it, then undo the choice. The sharper move is to extend only prefixes that can still become valid.

Keep two counts:

Add ( only while opened < n.
Add ) only while closed < opened.

def generate_parenthesis(n: int) -> list[str]:
    result: list[str] = []
    path: list[str] = []
 
    def search(opened: int, closed: int) -> None:
        if opened == n and closed == n:
            result.append("".join(path))
            return
 
        if opened < n:
            path.append("(")
            search(opened + 1, closed)
            path.pop()
 
        if closed < opened:
            path.append(")")
            search(opened, closed + 1)
            path.pop()
 
    search(0, 0)
    return result

The number of answers is the n-th Catalan number Cₙ, the count of valid balanced arrangements with n pairs. Writing each length-2 × n answer costs O(n), so time O(Cₙ · n). Space O(n) auxiliary for the path and call stack, excluding the output.

The pattern's pruning rule is the heart of the solution: once a prefix closes too much, no future character can repair it, so that branch never deserves a recursive call.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayn: int

Expected

[
  "()"
]

Run: visible + custom · Submit: full suite