Skip to main content
DSA patterns

Generate Parentheses

mediumRecursion Must-doGoogleMetaAmazon

Problem statement

You are given an integer n, the number of pairs of parentheses. Build every string of length 2n made only of ( and ) that is well-formed: every opening bracket has a matching closing bracket, and at no point while reading the string left to right have you seen more closing brackets than opening ones. Return all such strings, in any order.

This is the same "never let closes outrun opens" rule that governs any nested structure — matching brackets in a config file, balanced tags in generated markup, nested scopes in a parser — except here the task is to build every valid shape instead of checking a single one.

Examples

Example 1

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Explanation: with 3 pairs there are exactly 5 distinct well-formed arrangements — the 3rd Catalan number.

Example 2

Input: n = 1

Output: ["()"]

Explanation: with a single pair, () is the only way to place one opening and one closing bracket so that the closing bracket never comes first.

Hints

Hint 1: Trying every arrangement of 2n characters and checking each one for validity works, but it wastes time finishing strings whose very first few characters already broke the rule — is there a way to never build an invalid prefix in the first place?

Approach

Optimal: Closure number

Intuition

Every non-empty well-formed string has the shape ( + A + ) + B, where A and B are themselves well-formed strings (possibly empty). That is because the very first ( has to close somewhere, and everything between it and its matching ) is a self-contained valid block (A); whatever follows that matching ) is another valid block (B). If A uses c pairs, B must use the remaining n - 1 - c pairs. So every valid string for n pairs can be built by trying every split c from n - 1 down to 0, generating all valid strings for c pairs and for n - 1 - c pairs, and combining every pair of them. Iterating the split from the largest enclosed block down to the smallest happens to reproduce the same order as the backtracking approach.

Steps

  1. Base case: for 0 pairs, the only valid string is the empty string "".
  2. For n pairs, try every split c from n - 1 down to 0 — the number of pairs enclosed by the very first bracket's match.
  3. Recursively generate (and cache) all valid strings for c pairs (the "left" set) and for n - 1 - c pairs (the "right" set).
  4. For every left string A and every right string B, combine them as ( + A + ) + B and add the result.
  5. Once every split has been tried, the combined list holds every valid string for n pairs.

Dry run

n = 2, splits c = 1 then c = 0:

split c left set (generate(c)) right set (generate(1-c)) combined
1 ["()"] [""] "(" + "()" + ")" + "" = "(())"
0 [""] ["()"] "(" + "" + ")" + "()" = "()()"

Result: ["(())", "()()"] — the same combinations as backtracking, built from a different recursive split.

Edge cases: n = 0 sits outside this problem's constraints (n ≥ 1), but it is the base case, [""], that every other value of n is built from.

Complexity

Time O(4ⁿ / √n) - The same Catalan-number count of results is produced, and the recurrence Cₙ = Σ Cₖ · Cₙ₋₁₋ₖ mirrors how the Catalan numbers themselves grow, so the total work is the same order as backtracking, O(4ⁿ / √n), just organized around smaller cached subproblems instead of a single deep search.

Space O(n · Cₙ) - Caching the generated list for every pair count from 0 up to n so it can be reused across splits stores a constant-factor more strings than just the final answer for `n`, plus O(n) recursion depth while a cache entry is being built.

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        cache: dict[int, list[str]] = {0: [""]}

        def generate(pairs: int) -> list[str]:
            if pairs in cache:
                return cache[pairs]
            combos = []
            for c in range(pairs - 1, -1, -1):
                for left in generate(c):
                    for right in generate(pairs - 1 - c):
                        combos.append("(" + left + ")" + right)
            cache[pairs] = combos
            return combos

        return generate(n)


if __name__ == "__main__":
    def fmt(items: list[str]) -> str:
        return "[" + ",".join(f'"{s}"' for s in items) + "]"

    print(fmt(Solution().generateParenthesis(3)))
    print(fmt(Solution().generateParenthesis(1)))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "generate all valid arrangements of n pairs of parentheses" — a build-many, not check-one, bracket problem
  • Idea: backtrack with two counters (open, close); add ( only if open < n, add ) only if close < open
  • Cost: O(4ⁿ / √n) time, O(n) space — matches the growth of the nth Catalan number
  • Trap: using close <= open instead of close < open lets a closing bracket get ahead of the opens mid-string, producing invalid results
  • Remember: the closure-number method (( + smaller valid + ) + smaller valid) reaches the same count from a different recursive split

Interview follow-ups

  • What if you only need to count the valid combinations, not list them?

    You do not need to build any strings at all — the count is exactly the nth Catalan number, computable directly as Cₙ = C(2n, n) / (n + 1), or with a simple O(n) dynamic-programming recurrence Cₙ = Σ Cₖ · Cₙ₋₁₋ₖ for k from 0 to n − 1. This drops both time and space from exponential to O(n) (or O(n²) for the DP form), since the actual strings are never materialized.

  • Generate all combinations, but discard any that would exceed a maximum length before completion.

    Add the maximum length as an extra bound inside the same backtracking function: stop recursing, without recording anything, once open + close would exceed that bound, in addition to the existing open < n and close < open guards. This still only ever explores valid prefixes, so the pruning stays just as effective, and the time and space both shrink automatically because fewer full-length paths are ever reached.

  • n can now be a few hundred, but you only need one example valid string, not all of them, to smoke-test a parser.

    Skip the search entirely: a string like "()" repeated n times, or "(" * n + ")" * n, is already well-formed for any n, so it can be constructed directly in O(n) time and space. Running the full backtracking search only makes sense when every combination is actually needed, not just one.

Frequently asked questions

That is the brute force approach, and it does work — but it means building all 2^(2n) strings when only about 4ⁿ / n^1.5 of them, the nth Catalan number, are ever valid. Pruning as you go, the way backtracking does, means every recursive call is already working on a string that could still become valid, so no effort goes into a branch that is already broken partway through.

Valid Parentheses (LeetCode 20) walks one given string once, using a stack or a counter, to confirm it is balanced — that is a check. Generate Parentheses builds every possible balanced string from nothing, which needs a search: it has to explore choices and undo the ones that lead nowhere. That difference is exactly why backtracking, not a single linear pass, is the natural fit here.

close counts brackets already placed, and the guard decides whether one more is safe to add. If close already equals open, adding another ) would make closes outnumber opens at that point in the string — invalid. Requiring close to be strictly less than open guarantees that every prefix built so far has already seen at least as many opens as closes.

Anything with nested scope — config blocks, JSON or YAML brackets, matching tags in generated markup, or balanced calls in a templating engine — depends on the same "never let closes outrun opens" invariant this problem is built around. Interviewers use it to see whether a candidate reaches for backtracking with pruning, instead of generate-then-filter, once the space of candidates is exponential but the space of valid answers is far smaller.

No — LeetCode accepts any order for this problem, since the returned list is compared as a set of strings. The backtracking approach and the closure-number approach can produce the results in different orders (they happen to match here because both explore from the largest enclosed block first), and either order is accepted.