Every balanced string of n bracket pairs

Backtracking Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
out: list[str] = []

def grow(s: str, opened: int, closed: int, n: int) -> None:
    if len(s) == 2 * n:
        out.append(s)
        return
    if opened < n:
        grow(s + "(", opened + 1, closed, n)
    if closed < opened:
        grow(s + ")", opened, closed + 1, n)

grow("", 0, 0, 3)
print(len(out), out[0], out[-1])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 5 ((())) ()()()

Right: five strings, from fully nested to fully side by side.

The two counters guarantee every finished string is valid, so the run visits only useful branches.

Why not the others?
  • B 6 ((())) ()()(). There are five balanced strings for three pairs.
  • C 5 ()()() ((())). Trying '(' first puts the nested string first.

30-second answer

Build the string one character at a time with two counters. Add '(' while fewer than n are used; add ')' only while it would not close more than were opened. Every branch then ends in a valid string, so no checking is needed. Trying '(' first gives sorted output. The count is the n-th Catalan number, about 4ⁿ / n^1.5, and each string has 2n characters, so writing them out is O(4ⁿ/√n) time; the recursion is O(n) deep.

Practise saying it · 45 s. No recording, just a timer

Explain generating balanced bracket strings.

Say your answer out loud, then check which of these points you covered:

  • Two counters
  • Close only below opened
  • Catalan count

Deep dive

Pruning at each step means no invalid string is ever built.

Generating all 2²ⁿ strings and filtering works for tiny n only.

Catalan numbers also count tree shapes and mountain-range drawings.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def balanced(n: int) -> list[str]:
    out: list[str] = []
    chars: list[str] = []

    def grow(opened: int, closed: int) -> None:
        if closed == n:
            out.append("".join(chars))
            return
        if opened < n:
            chars.append("(")
            grow(opened + 1, closed)
            chars.pop()
        if closed < opened:  # never close more than opened
            chars.append(")")
            grow(opened, closed + 1)
            chars.pop()

    grow(0, 0)
    return out

Common mistakes

  • Allowing ')' when open and close counts are equal.
  • Building strings with + at every level, which is fine here but O(n) per step; a list and join is cleaner.

Senior take & follow-ups

Explain why every finished branch is valid; that is the point of the two-counter rule.

Follow-up questions

Think of your answer first, then open the hint.

  1. How many strings for n = 4?

    Show hint

    14.

  2. How do you check one string is balanced?

    Show hint

    One counter; fail if it goes negative, and require zero at the end.

What each operation costs: Depth First Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.