Why Backtracking and What Greedy Cannot Solve in DSA Typescript - Why It Works

Concept Flow - Why Backtracking and What Greedy Cannot Solve

Start Problem

↓

Try Greedy Approach

↓

Is Greedy Solution Optimal?

No→Use Backtracking

↓

Explore All Options

↓

Return Greedy Solution

↓

Backtrack on Failure

↓

Return Best Solution

Start with greedy; if it fails to find the best solution, backtracking tries all options by exploring and undoing choices.

Execution Sample

DSA Typescript

function solve() {
  // Greedy picks best immediate choice
  // Backtracking tries all choices
}

Shows greedy picks fast but may fail; backtracking tries all paths to find the best.

Execution Table

Step	Approach	Current Choice	Is Choice Final?	Action	Visual State
1	Greedy	Pick max immediate value	No	Select choice	[Choice1]
2	Greedy	Pick next max value	No	Select choice	[Choice1 -> Choice2]
3	Greedy	Pick next max value	Yes	Return solution	[Choice1 -> Choice2 -> Choice3]
4	Check Greedy Optimality	-	-	Is solution best?	No
5	Backtracking	Try Choice1	No	Explore deeper	[Choice1]
6	Backtracking	Try Choice2	No	Explore deeper	[Choice1 -> Choice2]
7	Backtracking	Try Choice3	Yes	Found solution	[Choice1 -> Choice2 -> Choice3]
8	Backtracking	Backtrack from Choice3	-	Undo last choice	[Choice1 -> Choice2]
9	Backtracking	Try Choice4	Yes	Found better solution	[Choice1 -> Choice2 -> Choice4]
10	Backtracking	Return best solution	-	Return	[Choice1 -> Choice2 -> Choice4]

💡 Backtracking explores all choices to find the best solution when greedy fails.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
Current Choice	-	Choice1	Choice2	Choice3	-	Choice1	Choice2	Choice3	Choice2	Choice4	Choice4
Solution Found	No	No	No	Yes	No	No	No	Yes	No	Yes	Yes
Best Solution	None	None	None	Choice1->2->3	None	None	None	Choice1->2->3	Choice1->2	Choice1->2->4	Choice1->2->4

Key Moments - 3 Insights

Why can't greedy always find the best solution?

Because greedy picks the best immediate choice without checking future consequences, it can miss better overall solutions as shown in step 4 where greedy's solution is not optimal.

How does backtracking ensure the best solution?

Backtracking tries all possible choices by exploring and undoing decisions (steps 5 to 9), ensuring no option is missed, so it finds the best solution.

Why do we backtrack (undo choices)?

Backtracking undoes choices (step 8) to explore other options that greedy might miss, allowing full search of all possibilities.

Visual Quiz - 3 Questions

Look at the execution table, what is the Current Choice at step 6?

A Choice3

B Choice2

C Choice1

D Choice4

💡 Hint

Check the 'Current Choice' column at step 6 in the execution_table.

At which step does the algorithm realize greedy is not optimal?

A Step 3

B Step 7

C Step 4

D Step 9

💡 Hint

Look for the step where 'Is solution best?' is checked in the execution_table.

If greedy was optimal, which step would be skipped?

A Step 5

B Step 4

C Step 8

D Step 10

💡 Hint

Backtracking exploration starts at step 5; if greedy is optimal, backtracking is not needed.

Concept Snapshot

Greedy picks the best immediate choice fast.
It may miss the best overall solution.
Backtracking tries all choices by exploring and undoing.
Use backtracking when greedy fails.
Backtracking guarantees finding the best solution.

Full Transcript

This concept shows why greedy algorithms sometimes fail to find the best solution because they only pick the best immediate choice without considering future options. When greedy fails, backtracking tries all possible choices by exploring and undoing decisions to find the best overall solution. The execution table traces steps where greedy picks choices quickly but misses the optimal solution, then backtracking explores all options, backtracks on failures, and finally returns the best solution. Key moments explain why greedy can fail, how backtracking works, and why undoing choices is important. The visual quiz tests understanding of these steps and choices.

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