Generate Parentheses in TypeScript: A Clean Backtracking Walkthrough

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 = 4
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
With four 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.

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 (open < n).
   • We can add a closing parenthesis if the number of opening parentheses used so far is greater than the number of closing parentheses (close < open).

The code achieves this using two functions:

• generateParenthesis(): This is the main function. It initialises an empty array result and an empty string current. It then calls the backtrack function to populate the result array.
• backtrack(): This function performs the backtracking. It takes the current string current, the counts of open and close parentheses used so far (open and close), the maximum number of pairs n, and the result array result.
  • 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 result 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.

Wrapping up

The 'Generate Parentheses' problem is a standard exercise for practising recursion and backtracking. This problem's complexity lies in ensuring that all generated parentheses combinations are valid. The TypeScript solution I've written and shared here does just that, hopefully in an efficient manner.