· By John Kavanagh

Generate Parentheses in TypeScript: A Clean Backtracking Walkthrough

A photograph of rows of matching shoes arranged in wooden shelving compartments.
Image by Priscilla Du Preez, licensed from Unsplash.

The 'Generate Parentheses' problem is a classic computer science challenge you might encounter during a coding interview or otherwise on the LeetCode‑type coding challenge websites. This problem tests not just your algorithmic skills but also your understanding of recursion and backtracking.

The objective is to generate all combinations of well‑formed parentheses for a given number n. A well‑formed parentheses string is defined as one that opens and closes correctly. Understanding how to tackle this problem efficiently is useful for web developers who often face tasks that involve string manipulation and recursion, and it also links nicely back to a previous article I wrote about validating matched parentheses.


Problem Statement

Given n pairs of parentheses, write a function to generate all combinations of well‑formed parentheses.

Some Examples:

Input: n = 1
Output: ["()"]
With only one pair of parentheses, the only possible well‑formed combination is ().

Input: n = 2
Output: ["(())", "()()"]
With two pairs of parentheses, you can either nest one pair within the other (()) or place them side‑by‑side ()().

Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
With three pairs, the combinations start to grow in number. You can nest them in various ways or combine nested and side‑by‑side arrangements.

Input: n = 0
Output: [""]
At the other end of the spectrum, with zero pairs, the only valid combination is an empty string.

The official challenge uses 1 to 8 pairs. The zero‑pair example is an extra behaviour supported by this implementation, rather than one of LeetCode's required inputs.


Solution Using Backtracking

Backtracking is a general algorithmic technique that incrementally explores all possible options to solve a problem and then reverts (backtracks) when it determines that a particular pathway is not leading to a solution. Essentially, backtracking involves making a series of choices, each leading to a new set of choices, until a solution is found or all options have been explored.

This type of technique is often used for solving constraint satisfaction problems, where you have to find a set of variables that satisfy specific constraints (for example, the N‑Queens problem or Sudoku).

In the case of generating all well‑formed parentheses, we can use backtracking to systematically build strings and then backtrack when the current string doesn't lead to a well‑formed parentheses pair (). This allows us to explore all possible combinations of parentheses whilst minimising unnecessary calculations.

In Code

Using TypeScript (or JavaScript), it is relatively straightforward to put together a solution that will run on the front end:

const generateParenthesis = (n: number): string[] => {
  const res: string[] = [];

  const backtrack = (s: string, left: number, right: number) => {
    if (s.length === 2 * n) {
      res.push(s);
      return;
    }

    if (left < n) backtrack(`${s}(`, left + 1, right);
    if (right < left) backtrack(`${s})`, left, right + 1);
  };

  backtrack('', 0, 0);

  return res;
};

How It Works

The idea here is to build each valid combination of parentheses by making a sequence of choices.

  1. Base Case:

    If the constructed string has reached its maximum possible length (which is 2 * n since each pair of parentheses contributes two characters), then we add it to our list of solutions.
  2. Recursive Case:

    At each step, we have two choices: add an opening parenthesis ( or a closing parenthesis ). However, these choices are constrained:
    • We can add an opening parenthesis if we haven't used all opening parentheses yet (left < n).
    • We can add a closing parenthesis if the number of opening parentheses used so far is greater than the number of closing parentheses (right < left).

The code achieves this using two functions:

  • generateParenthesis(n) creates the empty result array res, defines the nested backtrack function, and starts it with backtrack('', 0, 0). That call supplies the initial empty string directly. The function returns res after the search finishes.
  • backtrack(s, left, right) receives the string built so far and the counts of opening and closing parentheses used. It closes over n and res from generateParenthesis, rather than receiving them as arguments.
    • It starts by evaluating the base case: if the length of the current string is equal to twice the number of pairs (2 * n), this indicates that a valid sequence of parentheses has been constructed. This valid sequence is then added to the res array.
    • It then evaluates whether it can add either an opening or closing parenthesis whilst maintaining a valid sequence. If adding one of these options keeps the sequence valid, the function chooses that option and then recursively calls itself to continue building the sequence.

Counting the Answers and the Work

The number of answers is the nth Catalan number: Cₙ = (2n)! / (n! * (n + 1)!). It starts 1, 1, 2, 5, 14 for n from 0 to 4. Each returned string contains 2n characters, so writing all answers already requires proportional to n * Cₙ work and character storage. Backtracking avoids invalid prefixes, but it cannot make the requested output small.

For n of at least 1, O(n * Cₙ) is a useful time bound when we charge for constructing strings. The recursion has O(n) frames. This particular version passes a newly extended string into each call, so that frame count is not a complete character‑storage bound: if every live prefix is materialised separately, their lengths along one path sum to O(n²). Engines may share string storage internally. The retained answers require O(n * Cₙ) characters separately from that temporary work.

As a quick correctness check, n = 2 must produce two distinct answers and n = 3 must produce five. Counts alone are not enough: every prefix must contain at least as many opening parentheses as closing ones, and each complete result must contain exactly n of each. Those checks catch an invalid early closing parenthesis even when a test happens to get the right number of strings.


Wrapping Up

I like this example because the validity rule is visible at each choice. We add an opening parenthesis only whilst some remain, and a closing one only when it has an unmatched opening partner. That keeps invalid prefixes out of the search. The remaining cost comes from the growing number and length of the answers we actually asked for.


Have a complex web platform issue?

Tell me what is blocked, what has changed, and what needs to be true after the fix. I'll come back with a practical next step.