Generate Parentheses

Given an integer n, return every string that uses exactly n opening brackets ( and n closing brackets ) and is well-formed: reading left to right, no prefix ever contains more ) than (, and the counts are equal at the end.

Each valid string must appear exactly once. The strings may be returned in any order.

Example 1

Example 2

Example 3

Constraints

• 1 <= n <= 8

Pattern Path · Backtracking · problem 124 of 169

Start simple

Generate all 2²ⁿ bracket strings and keep those that pass a balance check: O(2²ⁿ · n) time.

The key idea

Build each answer left to right and only ever extend a prefix that can still become valid. Track opened and closed, the numbers of each bracket placed so far.

• Adding ( is allowed while opened < n.
• Adding ) is allowed while closed < opened, so it always has an unmatched ( to close.

These two rules are exactly the definition of well-formed, so every string that reaches length 2n is valid, and every valid string is reached, because at each position the valid string's next character satisfies one of the rules. Different choices at the same position lead to different strings, so nothing is produced twice.

Backtracking (append, recurse, pop) means no partial string is ever thrown away for being invalid: the search tree contains only useful branches. The number of answers is the n-th Catalan number, roughly 4ⁿ / (n^1.5), and each costs O(n) to copy out.

Complexity

• Time: O(4<sup>n</sup> / √n)
• Space: O(n) recursion depth, plus the output

Python

class Solution:
    def generateParenthesis(self, n):
        result = []
        current = []

        def build(opened, closed):
            if len(current) == 2 * n:
                result.append("".join(current))
                return
            if opened < n:  # room for another "("
                current.append("(")
                build(opened + 1, closed)
                current.pop()
            if closed < opened:  # a ")" has something to close
                current.append(")")
                build(opened, closed + 1)
                current.pop()

        build(0, 0)
        return result

JavaScript

var generateParenthesis = function(n) {
  const result = [];
  const current = [];

  function build(opened, closed) {
    if (current.length === 2 * n) {
      result.push(current.join(""));
      return;
    }
    if (opened < n) { // room for another "("
      current.push("(");
      build(opened + 1, closed);
      current.pop();
    }
    if (closed < opened) { // a ")" has something to close
      current.push(")");
      build(opened, closed + 1);
      current.pop();
    }
  }

  build(0, 0);
  return result;
};

What the interviewer is checking

This is a classic test of backtracking with pruning: can you state the two constraints that keep every partial string valid and avoid generate-and-filter?

Mistakes to avoid

• Allowing ) whenever closed < n, which produces strings like )(.
• Forgetting to undo the last choice (pop) after recursing when using a shared buffer.
• Generating every bracket string and filtering, which is far slower for n = 8.
• Producing duplicates by inserting pairs into smaller answers without deduplicating.

Follow-ups to expect

• How many strings are there for a given n? (The n-th Catalan number.)
• Generate them with dynamic programming. ("(" + A + ")" + B over splits.)
• Support several bracket types. (Track a stack of open types.)

In real software

Grammar-based fuzzers and test generators enumerate syntactically valid inputs (balanced brackets, nested tags, expression trees) with the same constrained backtracking.

Practice next