Marauder Bot

Problem

Given a number n, produce every distinct string of length 2n made up of n opening and n closing parentheses such that the parentheses are validly matched and nested at every point in the string.

Example. For n = 2, the valid strings are (()) and ()(): two combinations, out of the six possible arrangements of two opening and two closing parentheses.

Key idea

Generating all arrangements of the 2n characters and filtering out the invalid ones wastes enormous effort, since most arrangements are invalid and get discarded. A better approach builds the string one character at a time and only ever places a character that keeps the string a candidate for validity, so nothing invalid is ever fully constructed.

Track how many opening and closing parentheses have been placed so far. At each step, you may place an opening parenthesis as long as you have not yet used all n of them. You may place a closing parenthesis only if fewer closing parentheses have been placed than opening ones; that guarantees you never close a bracket that has nothing open to match. Explore both legal choices recursively, backtracking after each to try the other branch, until the string reaches length 2n, at which point it is guaranteed valid by construction and is added to the result.

Solution

function generateParenthesis(n: number): string[] {
  const result: string[] = [];
  const current: string[] = [];

  function backtrack(openCount: number, closeCount: number): void {
    // Full length reached: the string is guaranteed valid by construction.
    if (current.length === 2 * n) {
      result.push(current.join(''));
      return;
    }

    // Only place '(' if fewer than n opens have been used so far.
    if (openCount < n) {
      current.push('(');
      backtrack(openCount + 1, closeCount);
      current.pop();
    }

    // Only place ')' if it wouldn't outnumber the opens placed so far.
    if (closeCount < openCount) {
      current.push(')');
      backtrack(openCount, closeCount + 1);
      current.pop();
    }
  }

  backtrack(0, 0);
  return result;
}

Complexity

Time: O(4^n / √n). Bounded by the nth Catalan number, which counts the valid sequences, with O(n) work to build each.
Space: O(n). The recursion depth, aside from the space used to store the output itself.

Watch out for

The closing-parenthesis condition must be a strict less-than comparison against the opening count, not less-than-or-equal.
Remember to backtrack, undoing the last character, between exploring the opening and closing branches if building the string in a mutable buffer.

Pattern

This is constrained backtracking: enforce the validity rule during construction rather than checking it after the fact. The same shape, building incrementally and pruning illegal branches immediately, applies to problems like generating valid IP addresses or placing non-attacking queens.

Generate Parentheses