Generate Parentheses

Given n pairs of parentheses, return every well-formed combination as strings. (LC 22)

This is Valid Parentheses run in reverse, and it is the cleanest first backtracking problem: the choices are binary, and the pruning rule is something you already know.

The recipe

Say before you type: "I build the string one character at a time. I can add an open parenthesis while I've used fewer than n. I can add a close only while there are more opens than closes. Those two rules mean every string I complete is already valid, so there is nothing to filter at the end."

1. Track how many opens and closes you have used.
2. If the string has 2n characters, it is done: record it.
3. If open < n, you may add (: recurse.
4. If close < open, you may add ): recurse.
5. Nothing needs undoing, because the string is rebuilt on each call. (With a shared array you would push and pop. That is the choose, explore, un-choose shape.)

The code

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

  const build = (path: string, open: number, close: number): void => {
    if (path.length === 2 * n) { out.push(path); return; }
    if (open < n) build(path + "(", open + 1, close);
    if (close < open) build(path + ")", open, close + 1); // only if an open is waiting
  };

  build("", 0, 0);
  return out;
}

Why this shape

The slow way is to generate every string of 2n characters and keep the valid ones. That is 2^(2n) strings, almost all of them garbage. Backtracking prunes instead: the instant a prefix can never become valid (a close with nothing to close), you do not extend it.

The two conditions are the whole proof. open < n stops you using too many opens. close < open stops a close from ever coming first, which is exactly the rule Valid Parentheses checks with a stack. Build only prefixes that pass that check and every finished string passes it too.

The number of answers is the Catalan number: 1, 2, 5, 14, 42, 132 for n = 1 to 6. Knowing it is a handy sanity check on your output.

Complexity

	Cost	Because
Time	O(4ⁿ / √n)	That is the Catalan number of answers, times the 2n characters in each
Space	O(n)	The recursion is 2n deep, not counting the output

Say "exponential, because the output itself is exponential". The interviewer is not asking you to derive Catalan.

Traps

• close < open, not close < n. The second one allows ")(", and it builds strings that are invalid.
• Generating and then filtering works, and it is a fine first answer to say. Then name the waste and prune.
• Duplicates. The branching above cannot produce the same string twice. If you ever write a version that can (inserting a pair into every position of smaller answers is the usual one), you need a Set.
• Mutating a shared array and forgetting to pop. Building strings by concatenation avoids it, and costs nothing at this size.
• Returning early on n = 0. The empty string is the one answer, so [""], but LC does not test it.

The other answer: build from smaller answers

Every well-formed string is "(" + A + ")" + B where A and B are well-formed with fewer pairs between them. That gives a bottom-up version:

function generateParenthesis(n: number): string[] {
  const memo: string[][] = [[""]];
  for (let i = 1; i <= n; i++) {
    const cur: string[] = [];
    for (let k = 0; k < i; k++)
      for (const a of memo[k])
        for (const b of memo[i - 1 - k]) cur.push("(" + a + ")" + b);
    memo.push(cur);
  }
  return memo[n];
}

It is the same answer by a different argument, and a good one to offer if asked for a second approach.

The pattern this trains

Backtracking is choose, explore, un-choose, and the skill is the pruning rule that stops dead branches early. The same template solves Subsets (78), Permutations (46), Letter Combinations of a Phone Number (17), Combination Sum (39) and N-Queens (51). The trigger is "return all" or "generate every": the answer is a list of configurations, not a count.