Solution

We build every valid arrangement of n pairs of parentheses one character at a time, refusing at each step to write a character that could make the string invalid — so nothing ever needs to be thrown away.

The problem, in plain English

You have n opening brackets and n closing brackets, and you want every distinct way to line them up so the result is balanced — each ) matched to an earlier (. For n = 2 there are two arrangements: (()) and ()(). The task is to generate all of them without accidentally emitting a broken string like )( and without missing a valid one. The number of answers is the nth Catalan number, so there are 5 for n = 3 and 14 for n = 4.

The mental model

Picture building the string from left to right, one character at a time, while carrying two counts: open, how many ( you have written so far, and close, how many ). At any half-built string you have at most two moves — write a ( or write a ) — and two small rules decide which are legal. You may open a new bracket as long as you have not used all n of them (open < n). You may close a bracket only when there is an unmatched ( waiting for it (close < open). Obey those two rules and the string stays valid at every prefix, so you never build anything you would have to discard.

A first attempt

The most literal reading of "every well-formed string" is: generate every possible string of n ( and n ), then keep the ones that happen to be balanced. A string of length 2n where each position is either character has 2^(2n) possibilities; build them all and filter.

function generateParenthesesBrute(n) {
  const result = [];
  const total = 2 * n;

  // Build every length-2n string over the two characters.
  function build(current) {
    if (current.length === total) {
      if (isBalanced(current)) result.push(current);
      return;
    }
    build(current + '(');
    build(current + ')');
  }

  // Balanced = the running depth never goes negative and ends at zero.
  function isBalanced(s) {
    let depth = 0;
    for (const ch of s) {
      depth += ch === '(' ? 1 : -1;
      if (depth < 0) return false;
    }
    return depth === 0;
  }

  build('');
  return result;
}

This is correct, but wasteful. For n = 3 it builds all 2^6 = 64 strings to keep just 5; for n = 4 it builds 256 to keep 14. Almost everything it produces — like ))(((( or (((()) — is discarded. The waste comes from committing to characters that already doom the string: the moment you write a ) with no open bracket to match, every string starting that way is dead, yet the brute force keeps extending it. The fix is to never make that move in the first place.

The working solution

function generateParentheses(n) {
  const result = [];

  // Grow one string, carrying how many "(" and ")" we have placed.
  function backtrack(current, open, close) {
    // A finished string has used all n pairs — its length is 2n.
    if (current.length === 2 * n) {
      result.push(current);
      return;
    }
    // Open a new pair only while pairs remain unused.
    if (open < n) {
      backtrack(current + '(', open + 1, close);
    }
    // Close a pair only while one is open and unmatched — this is
    // exactly what keeps every prefix (and so every result) balanced.
    if (close < open) {
      backtrack(current + ')', open, close + 1);
    }
  }

  backtrack('', 0, 0);
  return result;
}

module.exports = { generateParentheses };

The two guards are the whole difference. open < n stops you from opening more than n pairs; close < open stops you from writing a ) unless there is an unmatched ( for it to close. Because close can never overtake open, the running depth never goes negative, so every string that reaches length 2n is already balanced — there is nothing left to filter. Where the brute force explored a branch and then checked it, here the check is the branch condition, so dead paths are never entered.

Walking through one call

Take generateParentheses(2). Start with an empty string and open = 0, close = 0.

• "" — is close < open? 0 < 0 is false, so ) is off the table; only ( is legal (open 0 < 2). Write it → "(", open = 1.
• "(" — both moves are legal now: open again (1 < 2) or close (0 < 1). The recursion tries both branches.
  • Down the open branch: "((", open = 2. Now open < n is false, so only ) is legal → "(()" → "(())", which hits length 4 and is recorded.
  • Down the close branch: "()", open = 1, close = 1. Here close < open is 1 < 1 — false — so only ( is legal → "()(" → "()()", recorded.

Two leaves, two strings: (()) and ()(). Notice the empty root has only one child — you can never start with ) — and the single split at "(" is what fans the tree out.

Gotchas

• The close guard is close < open, not close < n — comparing close against open is what keeps the string balanced. Using close < n would let you write ) before any matching (, producing garbage like )( for n = 1.
• Record only at length 2n — push a string when current.length === 2 * n, the point where all n opens and n closes are in place. Stopping at open === n alone is too early: at "((" for n = 2 you already have open === n but not a single closing bracket yet.
• You do not need to copy the string — JavaScript strings are immutable, so current + '(' builds a fresh string and the caller's current is untouched. If you instead build with a shared mutable array and push/pop, you must copy it (result.push(current.join(''))) before recording, or every entry ends up pointing at the same final value.
• n = 0 returns [''], not [] — the empty string is the one well-formed arrangement of zero pairs. The base case fires immediately (0 === 2 * 0) and records ''.

Going further

• Just the count — if you only need how many well-formed strings exist rather than the strings themselves, skip the generation: the answer is the nth Catalan number, C(2n, n) / (n + 1), computable in O(n).
• Other balanced structures — the same "carry two counts, guard each move" shape enumerates other Catalan-numbered objects: full binary trees with n internal nodes, triangulations of a polygon, valid stack push/pop sequences. Only the leaf-recording step changes.
• Build it iteratively — you can drop the recursion, either with an explicit stack that mimics the call frames, or with dynamic programming: every well-formed string of n pairs is ( + [a string of i pairs] + ) + [a string of n - 1 - i pairs], so you can combine smaller answers into larger ones.