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

Concept Flow - Why Backtracking and What Greedy Cannot Solve

Start Problem

↓

Try Greedy Approach

↓

Does Greedy Give Optimal?

No→Use Backtracking

↓

Explore All Options

↓

Solution Found

↓

End

Start with greedy; if it fails to find the best answer, backtracking tries all options to find the correct solution.

Execution Sample

DSA Javascript

function canPartition(nums) {
  function backtrack(i, sum) {
    if (i === nums.length) return sum === 0;
    return backtrack(i + 1, sum - nums[i]) || backtrack(i + 1, sum);
  }
  return backtrack(0, nums.reduce((a,b) => a + b, 0) / 2);
}

Backtracking tries all subsets to check if array can be split into two equal sum parts, which greedy cannot solve.

Execution Table

Step	Operation	Index i	Current Sum	Decision	Backtrack Calls	Visual State
1	Start backtrack	0	11 (half sum)	Try include nums[0]=1	Calls backtrack(1,10)	[]
2	Include nums[0]	1	10	Try include nums[1]=5	Calls backtrack(2,5)	[1]
3	Include nums[1]	2	5	Try include nums[2]=11	Calls backtrack(3,-6)	[1,5]
4	Include nums[2]	3	-6	Sum negative, backtrack	Return false	[1,5,11]
5	Exclude nums[2]	3	5	Try include nums[3]=5	Calls backtrack(4,0)	[1,5]
6	Include nums[3]	4	0	Sum zero found	Return true	[1,5,5]
7	Backtrack success	-	-	-	-	Subset found: [1,5,5]
8	End	-	-	-	-	Solution exists
9	Greedy attempt	-	-	Pick largest first	-	Fails to find equal partition

💡 Backtracking explores all subsets until sum zero found; greedy fails as it picks largest first without checking all options.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 6	Final
i	0	1	2	3	4	End
sum	11	10	5	5	0	0
Backtrack Calls	0	1	2	4	5	Success
Current Subset	[]	[1]	[1,5]	[1,5]	[1,5,5]	[1,5,5]

Key Moments - 3 Insights

Why does greedy fail to find the correct partition?

Greedy picks the largest numbers first without checking all combinations, so it misses subsets like [1,5,5] that sum correctly, as shown in execution_table rows 9 and 6.

How does backtracking explore all options?

Backtracking tries including and excluding each number recursively, exploring all subsets until it finds one that sums to half, as seen in execution_table rows 1-7.

Why is sum zero important in backtracking?

Sum zero means the chosen subset sums exactly to half the total, so partition is possible. This is the base case checked at step 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the current subset?

A [5, 11]

B [1, 5, 11]

C [1, 5, 5]

D []

💡 Hint

Check the Visual State column at step 6 in execution_table.

At which step does backtracking find a subset summing to zero?

A Step 4

B Step 6

C Step 2

D Step 9

💡 Hint

Look for 'Sum zero found' in the Decision column in execution_table.

If greedy tried picking smallest numbers first, what would change in the execution_table?

A Greedy might find the solution, changing step 9 outcome

B Sum zero would never be found

C Backtracking steps would be fewer

D No change at all

💡 Hint

Step 9 shows greedy fails picking largest first; picking smallest first might succeed.

Concept Snapshot

Backtracking tries all possible choices to find correct solutions.
Greedy picks locally best options but can miss global best.
Use backtracking when greedy fails.
Example: Partition problem needs backtracking.
Backtracking explores subsets recursively.
Greedy is faster but not always correct.

Full Transcript

This visualization shows why backtracking is needed when greedy algorithms fail. The example is the partition problem: can we split an array into two equal sum parts? Greedy tries picking the largest numbers first but misses the correct subset. Backtracking tries all subsets by including or excluding each number recursively. When the sum reaches zero, it means a valid partition is found. The execution table traces each step, showing the current index, sum, decisions, and subsets. Variable tracker shows how index and sum change. Key moments clarify why greedy fails and how backtracking explores all options. The quiz tests understanding of these steps. Remember, backtracking is slower but guarantees correct answers when greedy cannot.

Practice

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

easy

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

B. Because greedy algorithms always find the optimal solution faster than backtracking.

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 to previous steps to try different paths.

2. Step 2: Compare with greedy algorithm

   Greedy makes the best immediate choice without reconsidering, which can miss the correct solution in complex problems.

3. Final Answer:

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

4. Quick Check:

   Backtracking = explores all + undo [OK]

Hint: Backtracking tries all paths; greedy picks immediate best [OK]

Common Mistakes:

• Thinking greedy always finds the best solution
• Confusing memory usage between backtracking and greedy
• Assuming greedy can undo choices

2. Which of the following is the correct syntax to start a backtracking function in JavaScript?

easy

A. function backtrack = (path, options) => { /* code */ }

B. function backtrack(path, options) { /* code */ }

C. backtrack function(path, options) { /* code */ }

D. function backtrack[path, options] { /* code */ }

Solution

1. Step 1: Recall JavaScript function declaration syntax

   Functions are declared using the keyword 'function' followed by the name and parentheses with parameters.

2. Step 2: Check each option

   function backtrack(path, options) { /* code */ } uses correct syntax. function backtrack = (path, options) => { /* code */ } uses incorrect assignment syntax. backtrack function(path, options) { /* code */ } has wrong keyword order. function backtrack[path, options] { /* code */ } uses brackets incorrectly.

3. Final Answer:

   function backtrack(path, options) { /* code */ } -> Option B

4. Quick Check:

   Standard function declaration = function backtrack(path, options) { /* code */ } [OK]

Hint: Use 'function name(params) { }' for normal functions [OK]

Common Mistakes:

• Using '=' with function keyword incorrectly
• Mixing function declaration and expression syntax
• Using brackets [] instead of parentheses ()

3. What will be the output of the following code snippet?

function backtrack(nums, path, res) {
  if (path.length === nums.length) {
    res.push([...path]);
    return;
  }
  for (let i = 0; i < nums.length; i++) {
    if (path.includes(nums[i])) continue;
    path.push(nums[i]);
    backtrack(nums, path, res);
    path.pop();
  }
}

const result = [];
backtrack([1, 2], [], result);
console.log(result);

medium

A. [[1, 2]]

B. [[2, 1]]

C. [[1, 2], [2, 1]]

D. [[1], [2]]

Solution

1. Step 1: Understand the backtracking logic

   The function generates all permutations of the array [1, 2] by adding elements not already in the path.

2. Step 2: Trace the recursive calls

   First path: [1, 2], second path: [2, 1]. Both are added to result.

3. Final Answer:

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

4. Quick Check:

   Permutations of [1,2] = [[1,2],[2,1]] [OK]

Hint: Backtracking with includes avoids duplicates, generates permutations [OK]

Common Mistakes:

• Forgetting to pop after recursion
• Not checking if element is already in path
• Expecting only one permutation

4. Identify the bug in this backtracking code for generating subsets:

function subsets(nums) {
  const res = [];
  function backtrack(start, path) {
    res.push(path);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(0, []);
  return res;
}

medium

A. The function should return inside the loop.

B. The loop should start from 0 instead of start.

C. The pop() is missing after recursive call.

D. The code pushes the same path array reference, causing all results to be identical.

Solution

1. Step 1: Analyze how path is added to results

   The code pushes 'path' directly, which is a reference to the same array that changes over time.

2. Step 2: Understand consequences

   All entries in res will point to the same array, resulting in identical subsets at the end.

3. Final Answer:

   The code pushes the same path array reference, causing all results to be identical. -> Option D

4. Quick Check:

   Push copy of path, not reference [OK]

Hint: Push a copy of path (e.g., [...path]) to avoid reference bugs [OK]

Common Mistakes:

• Pushing path without copying
• Incorrect loop start index
• Missing pop after recursion

5. Given the problem of selecting a subset of items with weights and values to maximize value without exceeding weight limit, why can't a greedy algorithm always solve it correctly, and how does backtracking help?

Choose the best explanation.

hard

A. Greedy picks items with highest value first, which may exceed weight; backtracking tries all combinations to find the best fit.

B. Greedy always finds the best solution by sorting items by weight; backtracking is slower and unnecessary.

C. Greedy picks items randomly; backtracking sorts items before selection.

D. Greedy and backtracking both always find the same solution for this problem.

Solution

1. Step 1: Understand greedy approach limitations

   Greedy selects items based on immediate criteria (like highest value), which can lead to overweight or suboptimal total value.

2. Step 2: Understand backtracking advantage

   Backtracking explores all subsets, checking weight limits and total values, ensuring the optimal subset is found.

3. Final Answer:

   Greedy picks items with highest value first, which may exceed weight; backtracking tries all combinations to find the best fit. -> Option A

4. Quick Check:

   Greedy = local best, Backtracking = global best [OK]

Hint: Greedy fails on constraints; backtracking tries all combos [OK]

Common Mistakes:

• Assuming greedy always works for knapsack
• Thinking backtracking is always slower without benefit
• Confusing sorting criteria in greedy