Brian Baliach

Posted on Aug 14 • Originally published at balysnotes.com

Weekly Coding Challenge #2: Generating Parentheses with Backtracking and Recursion

#backtracking #recursion #typescript

I’m continuing the weekly challenge series, and this time we’re tackling a foundational favorite: Generate Parentheses. The goal is to produce all well-formed strings of parentheses for a given n pairs of parenthesis, and it’s a perfect showcase for two core ideas in algorithm design: backtracking and recursion. I’ll walk through the problem, explain why these techniques fit, and then break down the TypeScript implementation line by line.

Problem Overview

Here’s the problem statement:

You are given an integer n. Return all well-formed parentheses strings that you can generate with n pairs of parentheses.

You can also find a detailed problem statement here:
https://neetcode.io/problems/generate-parentheses?list=neetcode150

Also, here's my public GitHub repo that has all these coding solutions implemented:
https://github.com/TylerMutai/coding-challenges-solutions/tree/main/ts-coding-challenges-solutions

The task is to enumerate every valid combination, ensuring each string is balanced (every opening parenthesis has a matching closing one, and order is correct).

1. Understanding Backtracking and Recursion

Before diving into code, let’s clarify the two techniques driving the solution.

Backtracking is a systematic way to explore all possible configurations by making a sequence of choices, recursing deeper when a choice looks promising, and undoing it (“backtracking”) when it doesn’t. It shines when we need to generate combinations under constraints, which is exactly our situation.

Recursion is a function calling itself with smaller subproblems. Here, it naturally models "build the string one character at a time", carrying the current state along (how many open/closed parenthesis we’ve used) until we reach a complete, valid result. Together, recursion provides the structure of exploration, and backtracking provides the discipline to try, revert, and try again.

2. TypeScript Solution

Let’s look at the core implementation:

/**
 * You are given an integer n.
 * Return all well-formed parentheses strings that you can generate with n pairs of parentheses.
 */

const generateParenthesis = (n: number) => {

  const result: string[] = [];
  const stack: string[] = [];

  const backtrack = (openN: number, closeN: number) => {
    if (openN === closeN && openN === n && closeN === n) {
      result.push(stack.join(""));
    }

    if (openN < n) {
      stack.push("(");
      backtrack(openN + 1, closeN);
      stack.pop();
    }

    if (closeN < openN) {
      stack.push(")");
      backtrack(openN, closeN + 1);
      stack.pop();
    }
  };

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

console.log(generateParenthesis(3));

3. Step-By-Step Explanation

Let’s unpack the key decisions and constraints inside the algorithm.

a) State and Constraints

We track two counters:

openN: how many "(" we’ve used so far.
closeN: how many ")" we’ve used so far.

The constraints that keep the string valid:

We can’t use more than n opening parentheses:

  if (openN < n) { ... }

We can only close if we have an unmatched "(" available, which basically means we can't use a closing parenthesis if the currently open parenthesis are less than the closing parenthesis:

  if (closeN < openN) { ... }

These checks prevent invalid prefixes from ever forming.

b) The Backtracking Function

const backtrack = (openN: number, closeN: number) => { ... }

This function builds strings incrementally using a stack (array of characters) as our current path. At each call:

If we’ve placed n open parentheses and n closed parentheses, we have a complete, valid string and add it to our results array:

  if (openN === closeN && openN === n && closeN === n) {
    result.push(stack.join(""));
  }

Otherwise, we branch by choosing a "(" if allowed, or a ")" if it keeps the string valid. After exploring a branch, we pop to revert the choice and try the next option: this is the essence of backtracking.

c) Choosing "("

if (openN < n) {
  stack.push("(");
  backtrack(openN + 1, closeN);
  stack.pop();
}

We can always add another "(" as long as we haven’t used n of them. Push, explore deeper, then undo.

d) Choosing ")"

if (closeN < openN) {
  stack.push(")");
  backtrack(openN, closeN + 1);
  stack.pop();
}

We only add ")" if there are more opens than closed so far. This preserves balance at every prefix.

e) Building Results

The recursion starts at:

backtrack(0, 0);

The result array accumulates every well-formed string. Because we never create invalid prefixes, we don’t need to filter later. Every terminal path is valid by construction.

4. Example

Given this input:

generateParenthesis(3);

A valid output is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

All strings are balanced, and every unique combination is present.

Conclusion

By combining recursion’s natural tree structure with backtracking’s disciplined choice-and-revert strategy, we can generate all well-formed parentheses efficiently. The constraints (limit opens to n, never let closed exceed opens) ensure correctness without post-processing. It’s a clean and scalable pattern you’ll reuse across many combinatorial problems.

If you have questions or ideas for variations (like adding brackets or braces), drop a comment below.
See you in next week’s challenge!

DEV Community