
An active Player in the game of technology


Brian Baliach


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:

```plaintext
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:

```typescript
/**
 * 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:
  ```typescript
  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:
  ```typescript
  if (closeN < openN) { ... }
  ```

These checks prevent invalid prefixes from ever forming.

---

### b) The Backtracking Function

```typescript
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:
  ```typescript
  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 "("

```typescript
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 ")"

```typescript
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:
```typescript
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:

```typescript
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!


A step-by-step walkthrough of the Generate Parentheses problem using backtracking and recursion in TypeScript.

Showing posts from parentheses tag

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