Generate Parentheses

Difficulty: Medium

Problem

You have n pairs of round brackets and need to list every distinct way of arranging them so that each bracket is properly opened and closed. Write a function that returns all such balanced strings. Constraint: 1 <= n <= 8 (for n = 8 there are 1,430 strings).

Example

Input: n = 2
Output: ["(())","()()"]
Explanation: With 2 pairs, only these 2 arrangements are balanced.

Brute-force approach

This is a recursion-focused problem. We go directly to the recursive solution using the Leap of Faith approach.

Time complexity: - · Space complexity: -

Optimal approach

Key insight: At each position, you make a choice ('(' or ')'), trust recursion to handle everything after that choice, and the two rules (opens < n, closes < opens) guarantee every completed string is valid.

Use the Leap of Faith recipe: at each position, place '(' or ')' if allowed, and trust recursion to generate all valid continuations from there.

Steps

  1. Initialize empty result list
  2. Call backtrack('', 0, 0)
  3. Base case: if string length == 2n, add to result
  4. If opens < n, Leap of Faith: backtrack(path + '(', opens + 1, closes)
  5. If closes < opens, Leap of Faith: backtrack(path + ')', opens, closes + 1)
  6. Return result

Time complexity: O(4^n / √n) · Space complexity: O(n)

Pseudocode

function generateParenthesis(n):
    result = []
    backtrack(result, '', 0, 0, n)
    return result

function backtrack(result, path, opens, closes, n):
    if len(path) == 2 * n:
        result.append(path)
        return
    if opens < n:
        backtrack(result, path + '(', opens + 1, closes, n)
    if closes < opens:
        backtrack(result, path + ')', opens, closes + 1, n)

Hints

  • At each position, you can either add '(' or ')', but not always both
  • You can add '(' only if you haven't used all n opening parentheses yet
  • You can add ')' only if there are unmatched '(' to close (closes < opens)
  • When the string reaches length 2n, it's a valid combination
  • A ')' needs something waiting to be closed: the rule is strictly closes < opens (a tie means nothing is waiting).
  • Stop at length 2n: by then opens = closes = n, so neither rule allows another character, and this is the place to save the answer.

Complexity questions

What is the time complexity of generating all valid parentheses?

O(4^n / √n). The number of valid combinations is the nth Catalan number C(n) ≈ 4^n / (n^(3/2) * √π). Each string takes O(n) to construct. Total: O(n * C(n)) = O(4^n / √n), that is n times the Catalan count.

What is the space complexity (call stack depth)?

O(n). The pile holds at most 2n + 1 waiting calls (one per character placed, plus the starting call), which is O(n). The output list is extra space, not counted in that O(n). Note that the string version keeps a copy of the string in every waiting call (lengths 0 to 2n, about 2n^2 characters in total), while the list-with-undo version keeps one shared list, so it avoids that.

For n=3, how many strings does backtracking create vs brute force?

5 vs 64. Backtracking creates exactly 5 valid strings (the 3rd Catalan number). Brute force generates all 2^6 = 64 strings of '(' and ')'. Backtracking explores only valid paths: 92% of the work is pruned!

Check your understanding of Generate Parentheses

For n=2, why is ')(' NOT a valid combination?

The closing ')' appears before any opening '(', it has nothing to close. A ')' can only appear when there's a preceding unmatched '(' to pair with. In ')(', the first ')' has no matching '(' before it.

If someone magically generates all valid parentheses after placing '(' as the first character, what do you still need to do?

Nothing: those ARE some of the valid combinations. That's the Leap of Faith! If you place '(' first and trust the recursion to generate all valid continuations, those results are valid combinations. You also need to explore placing ')' first (if allowed), but the recursive calls handle each branch.

When building a string, when can we add a closing parenthesis ')'?

Only when closes < opens (there's an unmatched '(' to close). We can only add ')' when closes < opens, meaning there's at least one unmatched '(' waiting to be closed. This ensures we never have more ')' than '(' at any point.

Keep practising