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.

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 (open < n, close < open) 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 open < n, Leap of Faith: backtrack(current + '(', open + 1, close)
  5. If close < open, Leap of Faith: backtrack(current + ')', open, close + 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, current, open, close, n):
    if len(current) == 2 * n:
        result.append(current)
        return
    if open < n:
        backtrack(result, current + '(', open + 1, close, n)
    if close < open:
        backtrack(result, current + ')', open, close + 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 (close < open)
  • When the string reaches length 2n, it's a valid combination

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).

What is the space complexity (call stack depth)?

O(n). The maximum recursion depth is 2n (one level per character placed), which is O(n). Each frame uses O(1) extra space (just the counters). The output list takes additional space for storing results.

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 close count < open count (there's an unmatched '(' to close). We can only add ')' when close < open, meaning there's at least one unmatched '(' waiting to be closed. This ensures we never have more ')' than '(' at any point.

Keep practising