
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.

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


I've decided to do a new blog series where I’ll be sharing coding challenges I’ve solved each week. For our first entry, I’ll walk through the classic Subsets II problem, which involves returning all possible *unique* subsets in an integer array that may contain duplicates, demonstrating how to approach it, step by step, using one of the most fundamental algorithmic techniques: __backtracking__.

---

## Problem Overview

Here’s the problem statement:

```plaintext
You are given an array nums of integers, which may contain duplicates. Return all possible subsets.

The solution must not contain duplicate subsets. You may return the solution in any order.
```
You can also find a more detailed problem statement [here](https://neetcode.io/problems/subsets-ii?list=neetcode150).

The goal is to produce every possible subset from the input array, while ensuring that no duplicate subsets are included in the output. This is a common scenario when dealing with arrays that can have repeated elements.

---

## 1. Understanding Backtracking

Before diving into the implementation, it’s important to clarify what backtracking is and why it fits this problem.

Backtracking is an algorithmic approach often used for searching through all possible decisions in a sequence, systematically exploring all configurations and undoing ('backtracking') steps as necessary. It’s particularly effective for generating all possible combinations or permutations.

In the context of Subsets II, backtracking enables us to explore every possible way to build a subset, one element at a time, and carefully manage the inclusion of duplicates.

---

## 2. TypeScript Solution

Let’s look at the core implementation:

```typescript
/**
 * Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
 * The solution set must not contain duplicate subsets. Return the solution in any order.
 */

const subsetsWithDup = (nums: number[]) => {

  const backtrack = (start: number, subset: number[], nums: number[], res: number[][]) => {
    res.push([...subset]);
    for (let i = start; i < nums.length; i++) {
      // Skip duplicates
      if (i > start && nums[i] === nums[i - 1]) {
        continue;
      }
      subset.push(nums[i]);
      backtrack(i + 1, subset, nums, res);
      subset.pop();
    }
  };

  const res: number[][] = [];
  nums.sort((a: number, b: number) => a - b);
  backtrack(0, [], nums, res);
  return res;
};

console.log(subsetsWithDup([1, 2, 2]));
```

---

## 3. Step-By-Step Explanation

Let’s break down the solution, focusing on each step and decision.

---

### a) Sorting the Input

```typescript
nums.sort((a: number, b: number) => a - b);
```

The array is sorted first. This is essential for detecting duplicates efficiently. If duplicate numbers are adjacent, it’s much easier to skip them during subset generation.

---

### b) The Backtracking Function

```typescript
const backtrack = (start: number, subset: number[], nums: number[], res: number[][]) => { ... }
```

This function explores all possible subset combinations from a given start index in `nums`. Here’s what happens inside:

- **Add Current Subset:**  
  At each stage, add a _copy_ of the current subset to the result list:
  ```typescript
  res.push([...subset]);
  ```

- **Iterate From Start Index:**  
  For each possible next element (starting from the current index), we consider two options: include or skip.

- **Skip Duplicates:**  
  The key line that avoids duplicate subsets:
  ```typescript
  if (i > start && nums[i] === nums[i - 1]) {
    continue;
  }
  ```
  This ensures that, from the same decision point, we don’t select the same value twice.

- **Include Element, Explore Further:**  
  We add the current element, proceed to the next index, and then remove the element ('backtrack') for subsequent branches:
  ```typescript
  subset.push(nums[i]);
  backtrack(i + 1, subset, nums, res);
  subset.pop();
  ```

---

### c) Generating Results

The process starts with an empty subset and fills the `res` array with every unique subset generated through the backtracking process.

---

## 4. Example

Given this input:

```typescript
subsetsWithDup([1, 2, 2]);
```

The output will be:

```
[
  [],
  [1],
  [1, 2],
  [1, 2, 2],
  [2],
  [2, 2]
]
```

Each subset is unique, and all possible combinations are present.

---

## Conclusion

By applying backtracking and carefully managing duplicate handling using sorting and an early-skip condition, we can efficiently generate all unique subsets of an array with duplicates. This approach is both scalable and easy to implement, making it a strong fit for this class of problems.

If you have any questions, suggestions, or feedback, feel free to leave a comment. 
Stay tuned for next week’s challenge!


A clear, step-by-step walkthrough of the Subsets II problem, using backtracking in TypeScript.

Showing posts from typescript category

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

Weekly Coding Challenge #1: Solving Subsets II with Backtracking