Why Backtracking and What Greedy Cannot Solve in DSA Typescript - Why This Pattern

Mental Model

Backtracking tries all possible choices step-by-step to find the right answer, while greedy picks the best choice now but might miss the best overall.

Analogy: Imagine choosing a path in a maze: greedy picks the closest exit at each turn but might get stuck; backtracking tries every path until it finds the exit.

Start
  ↓
Choice 1 -> Dead end
  ↓
Choice 2 -> Possible path -> Goal

Dry Run Walkthrough

Input: Find subset of numbers [3, 1, 7, 9] that sums to 11

Goal: Show greedy picks wrong subsets, backtracking finds correct subset

Step 1: Greedy picks largest number 9 first

[9] sum=9

Why: Greedy chooses biggest number to get close to 11 quickly

Step 2: Greedy tries to add next largest number 7 but sum exceeds 11

[9] sum=9 (cannot add 7)

Why: Adding 7 makes sum 16 which is too big

Step 3: Greedy tries next number 3 but sum exceeds 11 again

[9] sum=9 (cannot add 3)

Why: Adding 3 makes sum 12 which is too big

Step 4: Greedy tries next number 1 and sum becomes 10

[9,1] sum=10

Why: Adding 1 reaches sum 10 but target is 11

Step 5: Backtracking tries subsets starting from empty set

[] sum=0

Why: Backtracking explores all options

Step 6: Backtracking adds 3, sum=3

[3] sum=3

Why: Try including 3

Step 7: Backtracking adds 1 then 7, sum=11 found

[3,1,7] sum=11

Why: Found subset that sums exactly to 11

Result:

[3,1,7] sum=11 is correct subset found by backtracking; greedy found [9,1] sum=10 but failed to reach target

Annotated Code

DSA Typescript

class SubsetSum {
  nums: number[];
  target: number;

  constructor(nums: number[], target: number) {
    this.nums = nums;
    this.target = target;
  }

  greedySolution(): number[] {
    let sum = 0;
    const result: number[] = [];
    // Sort descending for greedy pick
    const sorted = [...this.nums].sort((a, b) => b - a);
    for (const num of sorted) {
      if (sum + num <= this.target) {
        result.push(num); // add number if sum not exceeded
        sum += num;
      }
      if (sum === this.target) {
        break; // stop if target reached
      }
    }
    return result;
  }

  backtrackingSolution(): number[] {
    const result: number[] = [];
    const path: number[] = [];

    const backtrack = (index: number, currentSum: number): boolean => {
      if (currentSum === this.target) {
        result.push(...path); // found valid subset
        return true;
      }
      if (currentSum > this.target || index === this.nums.length) {
        return false; // stop if sum exceeded or no more numbers
      }

      // choose current number
      path.push(this.nums[index]);
      if (backtrack(index + 1, currentSum + this.nums[index])) {
        return true; // found solution
      }
      path.pop(); // backtrack

      // skip current number
      if (backtrack(index + 1, currentSum)) {
        return true; // found solution skipping current
      }

      return false; // no solution found here
    };

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

// Driver code
const nums = [3, 1, 7, 9];
const target = 11;
const subsetSum = new SubsetSum(nums, target);

console.log('Greedy solution:', subsetSum.greedySolution().join(', '));
console.log('Backtracking solution:', subsetSum.backtrackingSolution().join(', '));

const sorted = [...this.nums].sort((a, b) => b - a);

sort numbers descending for greedy choice

if (sum + num <= this.target) { result.push(num); sum += num; }

add number if sum does not exceed target

if (currentSum === this.target) { result.push(...path); return true; }

found subset that sums exactly to target

if (currentSum > this.target || index === this.nums.length) { return false; }

stop exploring if sum exceeded or no more numbers

path.push(this.nums[index]); if (backtrack(index + 1, currentSum + this.nums[index])) { return true; } path.pop();

try including current number and recurse

if (backtrack(index + 1, currentSum)) { return true; }

try skipping current number and recurse

Output

Greedy solution: 9, 1

Backtracking solution: 3, 1, 7

Complexity Analysis

Time: O(2^n) because backtracking tries all subsets, greedy is O(n log n) due to sorting

Space: O(n) for recursion stack and path storage in backtracking, O(n) for sorting in greedy

vs Alternative: Greedy is faster but can miss solutions; backtracking is slower but finds all valid subsets

Edge Cases

empty input array

backtracking returns empty subset, greedy returns empty subset

DSA Typescript

if (currentSum > this.target || index === this.nums.length) { return false; }

no subset sums to target

backtracking returns empty array, greedy returns partial sum subset

DSA Typescript

if (currentSum === this.target) { return true; }

target is zero

backtracking returns empty subset immediately, greedy returns empty subset

DSA Typescript

if (currentSum === this.target) { return true; }

When to Use This Pattern

When a problem asks for all or some combinations that satisfy a condition and greedy fails, reach for backtracking to explore all possibilities.

Common Mistakes

Mistake: Using greedy approach expecting it to always find correct subset sum
Fix: Use backtracking to explore all subsets when greedy fails

Mistake: Not backtracking (undoing) after trying a choice
Fix: Always remove last choice before trying next option to explore all paths

Summary

Backtracking tries all possible choices to find correct solutions where greedy fails.

Use backtracking when greedy choices do not guarantee correct or complete answers.

The key is exploring all options step-by-step and undoing choices to find the right path.

Practice

1. Why is backtracking preferred over greedy algorithms for solving problems like the N-Queens puzzle?

easy

A. Because greedy algorithms always find the optimal solution faster

B. Because backtracking explores all possible solutions and can undo choices, while greedy makes irreversible choices

C. Because backtracking uses less memory than greedy algorithms

D. Because greedy algorithms are only used for sorting problems

Solution

1. Step 1: Understand backtracking's approach

   Backtracking tries all possible options and can go back (undo) if a choice leads to failure.

2. Step 2: Compare with greedy approach

   Greedy algorithms make the best immediate choice but cannot undo it, so they may miss the correct solution.

3. Final Answer:

   Because backtracking explores all possible solutions and can undo choices, while greedy makes irreversible choices -> Option B

4. Quick Check:

   Backtracking = explores all + undo [OK]

Hint: Backtracking tries all paths; greedy picks one path only [OK]

Common Mistakes:

• Thinking greedy always finds the best solution
• Confusing backtracking with brute force
• Believing backtracking uses less memory

2. Which of the following TypeScript code snippets correctly represents the start of a backtracking function signature?

easy

A. function backtrack(path number[], options number[]): void

B. function backtrack(path: number[], options: number[]) => void

C. function backtrack(path: number[], options: number[]): void

D. function backtrack(path: number[], options: number[]): number

Solution

1. Step 1: Check TypeScript function syntax

   Correct syntax uses colon ':' to specify types and parentheses for parameters.

2. Step 2: Verify return type and arrow usage

   function backtrack(path: number[], options: number[]): void uses correct syntax with void return type; others have syntax errors or wrong return type.

3. Final Answer:

   function backtrack(path: number[], options: number[]): void -> Option C

4. Quick Check:

   Correct TypeScript function syntax = function backtrack(path: number[], options: number[]): void [OK]

Hint: Look for colons and parentheses in function parameters [OK]

Common Mistakes:

• Missing colons between parameter and type
• Using arrow '=>' incorrectly in function signature
• Wrong return type specified

3. Consider this TypeScript backtracking code snippet for generating subsets:

function backtrack(start: number, path: number[], nums: number[], result: number[][]) {
  result.push([...path]);
  for (let i = start; i < nums.length; i++) {
    path.push(nums[i]);
    backtrack(i + 1, path, nums, result);
    path.pop();
  }
}

const nums = [1, 2];
const result: number[][] = [];
backtrack(0, [], nums, result);
console.log(result);

What is the output printed?

medium

A. [[], [2], [1, 2], [1]]

B. [[1], [2]]

C. [[1, 2]]

D. [[], [1], [1, 2], [2]]

Solution

1. Step 1: Trace backtracking calls with nums = [1, 2]

   Start with empty path [], add it to result. Then add 1, recurse, add [1], add 2, recurse, add [1,2], backtrack, add 2 alone, add [2].

2. Step 2: Collect all subsets generated

   Subsets are [], [1], [1, 2], and [2] in order.

3. Final Answer:

   [[], [1], [1, 2], [2]] -> Option D

4. Quick Check:

   All subsets generated = [[], [1], [1, 2], [2]] [OK]

Hint: Backtracking with push/pop generates all subsets including empty [OK]

Common Mistakes:

• Forgetting to add empty subset
• Not popping after recursion causing wrong subsets
• Mixing order of subsets

4. The following TypeScript backtracking code tries to find all permutations of [1, 2], but it has a bug:

function permute(nums: number[], path: number[], used: boolean[], result: number[][]) {
  if (path.length === nums.length) {
    result.push(path);
    return;
  }
  for (let i = 0; i < nums.length; i++) {
    if (used[i]) continue;
    path.push(nums[i]);
    used[i] = true;
    permute(nums, path, used, result);
    path.pop();
    used[i] = false;
  }
}

const result: number[][] = [];
permute([1, 2], [], [false, false], result);
console.log(result);

What is the bug and how to fix it?

medium

A. Bug: Pushing path directly causes reference issues; fix by pushing a copy of path

B. Bug: used array is not updated correctly; fix by removing used[i] = false

C. Bug: Base case condition is wrong; fix by changing path.length === nums.length to path.length > nums.length

D. Bug: Loop should start from 1 instead of 0; fix by changing for loop start

Solution

1. Step 1: Identify the problem with pushing path

   Pushing path directly adds the same array reference multiple times, causing all entries to be the same final path.

2. Step 2: Fix by pushing a copy of path

   Use result.push([...path]) to push a new array copy each time.

3. Final Answer:

   Bug: Pushing path directly causes reference issues; fix by pushing a copy of path -> Option A

4. Quick Check:

   Push copy of path, not reference [OK]

Hint: Always push a copy of path in backtracking results [OK]

Common Mistakes:

• Pushing path reference instead of copy
• Incorrect base case condition
• Misusing used array updates

5. You want to solve the classic "Subset Sum" problem: given an array of positive integers and a target sum, find if any subset sums exactly to the target. Why can't a greedy algorithm solve this correctly in all cases, and how does backtracking help?

hard

A. Greedy fails because picking largest numbers first may miss exact sum; backtracking tries all subsets to find exact match

B. Greedy fails because it sorts the array; backtracking sorts and tries subsets

C. Greedy fails because it uses recursion; backtracking uses iteration

D. Greedy fails because it only works on sorted arrays; backtracking only works on unsorted arrays

Solution

1. Step 1: Understand greedy approach limitation

   Greedy picks the largest numbers first, which may overshoot or miss the exact target sum.

2. Step 2: How backtracking solves the problem

   Backtracking tries all subsets by including or excluding each number, ensuring it finds an exact sum if it exists.

3. Final Answer:

   Greedy fails because picking largest numbers first may miss exact sum; backtracking tries all subsets to find exact match -> Option A

4. Quick Check:

   Subset sum needs all subsets tried = Greedy fails because picking largest numbers first may miss exact sum; backtracking tries all subsets to find exact match [OK]

Hint: Subset sum needs all subsets; greedy picks only some [OK]

Common Mistakes:

• Thinking greedy always finds exact sum
• Confusing sorting with solving approach
• Believing backtracking is iterative only