Why Backtracking and What Greedy Cannot Solve in DSA Javascript - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Subset Sum

What is the output of the following JavaScript code that uses backtracking to find all subsets of an array that sum to 5?

DSA Javascript

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

const nums = [1, 2, 3, 4];
const target = 5;
const result = [];
backtrack(nums, target, 0, [], result);
console.log(result);

A [[1,2,3],[1,4],[2,3]]

B [[1,2,3,4]]

C [[1,4],[2,3],[5]]

D [[1,4],[2,3]]

💡 Hint

Think about which subsets of [1,2,3,4] add exactly to 5 without repeating elements.

The backtracking function finds all unique subsets that sum to 5. The subsets [1,4] and [2,3] sum to 5. The subset [1,2,3] sums to 6, so it is excluded. There is no single element 5 in the array, so [5] is invalid. The full array sums to 10, so [1,2,3,4] is invalid.

🧠 Conceptual

intermediate

Why Greedy Fails for Subset Sum

Why does a greedy algorithm fail to find the correct solution for the subset sum problem?

A Because greedy algorithms make local optimal choices that may not lead to a global solution.

B Because greedy algorithms always try all possible subsets, which is inefficient.

C Because greedy algorithms require sorting the array first, which is impossible for subset sum.

D Because greedy algorithms only work for problems with negative numbers.

💡 Hint

Think about how greedy picks elements step-by-step without reconsidering previous choices.

Greedy algorithms pick the best option at each step without considering future consequences. For subset sum, this can miss combinations that add up correctly because it doesn't explore all possibilities.

🔧 Debug

advanced

Identify the Error in Greedy Coin Change

What error does the following greedy coin change code produce when trying to make change for 6 with coins [1, 3, 4]?

DSA Javascript

function greedyChange(coins, amount) {
  coins.sort((a,b) => b - a);
  let count = 0;
  for (let coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      count++;
    }
  }
  return count;
}

console.log(greedyChange([1,3,4], 6));

A Returns 6, which is the amount itself.

B Returns 3, which is correct minimum coins needed.

C Returns 3, which is incorrect minimum coins needed.

D Throws a TypeError because coins is not sorted properly.

💡 Hint

Check how the greedy picks coins starting from the largest coin.

The code sorts coins descending to [4,3,1]. For amount=6: picks 4 once (amount=2, count=1), skips 3 (2 < 3), picks 1 twice (amount=0, count=3). Returns 3.

Minimum coins needed is 2 (3+3). Greedy returns suboptimal solution of 3 coins.

❓ Predict Output

advanced

Backtracking vs Greedy Output Comparison

Given the array [2, 4, 6, 8] and target sum 8, what is the output of the backtracking and greedy algorithms below?

DSA Javascript

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

function greedy(nums, target) {
  nums.sort((a,b) => b - a);
  let res = [];
  for (let coin of nums) {
    if (coin <= target) {
      res.push(coin);
      target -= coin;
    }
  }
  return res;
}

const nums = [2,4,6,8];
const target = 8;
const backRes = [];
backtrack(nums, target, 0, [], backRes);
const greedyRes = greedy(nums, target);
console.log({backRes, greedyRes});

A {"backRes":[[2,6],[8]],"greedyRes":[8]}

B {"backRes":[[2,6],[8]],"greedyRes":[6,2]}

C {"backRes":[[2,6],[8]],"greedyRes":[4,2]}

D {"backRes":[[2,6],[8]],"greedyRes":[4,4]}

💡 Hint

Check how backtracking finds all subsets and greedy picks largest coins first.

Backtracking finds subsets [2,6] and [8] that sum to 8. Greedy picks the largest coin 8 first, so greedyRes is [8].

🚀 Application

expert

Choosing Backtracking Over Greedy in Puzzle Solving

You have a puzzle where you must select numbers from an array to reach a target sum exactly. Why is backtracking preferred over greedy in this case?

A Because backtracking always finds the solution in linear time, unlike greedy.

B Because backtracking explores all possible combinations ensuring no solution is missed, while greedy may miss valid solutions by making local choices.

C Because greedy algorithms are slower and use more memory than backtracking.

D Because greedy algorithms cannot handle arrays with more than 10 elements.

💡 Hint

Think about completeness and correctness of solutions.

Backtracking tries all possible combinations, so it guarantees finding a solution if one exists. Greedy makes local choices that may miss the correct combination.

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