Coding interview problems › Backtracking

🧩 Backtracking Medium

Generate Parentheses

Generate Parentheses explained: build only valid bracket strings with two counters and backtracking, tested Python, Catalan-number complexity and a live visual.

Also searched as: generate all balanced parentheses · valid parentheses combinations of n pairs · generate parentheses backtracking

🧩

Try it live Free

Backtracking: Subsets, Permutations & Pruning

In the Backtracking lab, turn pruning on and watch the explored-node counter collapse while the answers stay the same; the two counters here are that pruning rule.

Also useful: Stacks & the Monotonic Stack

Open the playground →

The problem

Given n, return every string of n pairs of parentheses that is well-formed (every opening bracket is closed in the right order).

Inputn = 3
Output["((()))", "(()())", "(())()", "()(())", "()()()"]
Inputn = 1
Output["()"]

The key insight

Do not generate all 22n strings and filter. Build the string left to right and only make legal moves: you may add ( while you have used fewer than n, and you may add ) only while there are more opens than closes. Every string that reaches length 2n is then valid by construction.

Brute force first: Generate all 22n bracket strings and test each for balance: correct but mostly wasted work.

Step-by-step approach

  1. Track opened and closed counts and the current string.
  2. If the string has length 2n, record it.
  3. If opened < n, add ( and recurse.
  4. If closed < opened, add ) and recurse.
  5. Undo each addition after its recursive call (or pass new strings so there is nothing to undo).

Python solution

PYTHON 3tested
def generate_parenthesis(n):
    out, path = [], []

    def dfs(opened, closed):
        if len(path) == 2 * n:
            out.append("".join(path))
            return
        if opened < n:
            path.append("(")
            dfs(opened + 1, closed)
            path.pop()
        if closed < opened:            # only close what is open
            path.append(")")
            dfs(opened, closed + 1)
            path.pop()

    dfs(0, 0)
    return out

Complexity

TimeO(4^n / √n)
SpaceO(n)

The number of valid strings is the n-th Catalan number, about 4n / (n1.5), and each costs O(n) to build. The recursion is 2n deep.

Common mistakes

Frequently asked questions

What is the time and space complexity of Generate Parentheses?

The output has Catalan(n) strings, about 4^n / n^1.5, each of length 2n, so time is roughly O(4^n / √n). The recursion uses O(n) space besides the output.

Why does the closed < opened rule guarantee validity?

A bracket string is balanced exactly when no prefix has more closes than opens and the totals are equal. The rule enforces the first condition at every step and the length check with opened ≤ n enforces the second.

How many valid strings are there for n pairs?

The n-th Catalan number: 1, 1, 2, 5, 14, 42, 132 for n = 0 to 6.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Backtracking Backtracking: Subsets, Permutations & Pruning lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.