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

Generate Parentheses – Solution & Complexity

Interview solutions
/
Generate Parentheses

Solution Walkthrough

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. 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. 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. 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. 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. 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. 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. 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)Letter Combinations of a Phone Number solution (medium)Palindrome Partitioning solution (medium)Permutations solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?