{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Generate Parentheses – Solution & Complexity

Interview solutions
/
Generate Parentheses

Solution Walkthrough

  1. Step 1: Understand the search tree

    • Every answer is a length-2n string built one character at a time.
    • A prefix is only worth continuing if it can still become valid: you can never close more parentheses than you have opened, and you can never open more than n.
    • The required output order comes naturally if every recursive call tries ( before ).

  2. Step 2: Start from a brute-force baseline

    • A direct baseline is to generate every length-2n string of ( and ), then keep only the balanced ones.
    • This is correct and still respects the required order if you branch to ( before ), but it wastes time exploring obviously impossible prefixes.
    def generate_parenthesis(n: int) -> list[str]:
    result: list[str] = []

    def is_valid(s: str) -> bool:
        balance = 0
        for ch in s:
            if ch == "(":
                balance += 1
            else:
                balance -= 1
                if balance < 0:
                    return False
        return balance == 0

    def build(current: list[str]) -> None:
        if len(current) == 2 * n:
            candidate = "".join(current)
            if is_valid(candidate):
                result.append(candidate)
            return

        current.append("(")
        build(current)
        current.pop()

        current.append(")")
        build(current)
        current.pop()

    build([])
    return result

  3. Step 3: Prune invalid prefixes early

    • Instead of generating bad strings and rejecting them later, track how many opens and closes you have used so far.
    • You may add ( only while open_count < n, and you may add ) only while close_count < open_count.
    • Those two rules guarantee every recursive prefix can still lead to a valid answer.

  4. Step 4: Optimal backtracking solution

    • This DFS builds only valid prefixes and automatically emits answers in the required canonical order because every call tries ( before ).
    • Once the current string reaches length 2n, it is a complete answer.
    def generate_parenthesis(n: int) -> list[str]:
    result: list[str] = []

    def backtrack(current: list[str], open_count: int, close_count: int) -> None:
        if len(current) == 2 * n:
            result.append("".join(current))
            return

        if open_count < n:
            current.append("(")
            backtrack(current, open_count + 1, close_count)
            current.pop()

        if close_count < open_count:
            current.append(")")
            backtrack(current, open_count, close_count + 1)
            current.pop()

    backtrack([], 0, 0)
    return result

  5. Step 5: Dry run

    Trace n = 3 with the optimal recursion.

    1. Start with "", so the only legal move is (.
    2. Repeatedly preferring ( first reaches "((()", then "((())", then "((()))", which becomes the first answer.
    3. Backtrack one step at a time to the nearest prefix that still allows a different valid choice, producing "(()())", then "(())()", then "()(())", then "()()()".

    Because every branch tries ( before ), the results appear as ["((()))","(()())","(())()","()(())","()()()"].

  6. Step 6: Common mistakes and follow-ups

    • Appending ) when close_count == open_count, which creates an invalid prefix immediately.
    • Forgetting to undo the last append before exploring the sibling branch.
    • Returning a set or sorting afterward can hide bugs in the required canonical order.
    • Follow-up: count combinations with Catalan DP when you need only the number, not the actual strings.

  7. Step 7: Edge cases to test mentally

    • n = 0 should return [""], not [], because there is one valid empty construction.
    • n = 1 returns exactly ["()"].
    • Larger n values explode in output size, so the algorithm should avoid generating invalid branches at all.

  8. Step 8: Final full solution and complexity

    Backtracking with ( opens first, ) second explores only valid prefixes, so it emits every well-formed string exactly once in canonical order. The runtime is O(C_n * n) and the output dominates space at O(C_n * n), where C_n is the nth Catalan number; recursion itself uses O(n) extra stack space.

    def generate_parenthesis(n: int) -> list[str]:
    result: list[str] = []

    def backtrack(current: list[str], open_count: int, close_count: int) -> None:
        if len(current) == 2 * n:
            result.append("".join(current))
            return

        if open_count < n:
            current.append("(")
            backtrack(current, open_count + 1, close_count)
            current.pop()

        if close_count < open_count:
            current.append(")")
            backtrack(current, open_count, close_count + 1)
            current.pop()

    backtrack([], 0, 0)
    return result

FAQ

See also

Practice Generate Parentheses online (run code in the browser)Combination Sum solution (medium)Combination Sum III solution (medium)Decode String solution (medium)Letter Combinations of a Phone Number solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?