Why Backtracking and What Greedy Cannot Solve in DSA Javascript - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a subset sum exists using backtracking.

DSA Javascript

function isSubsetSum(arr, n, sum) {
  if (sum === 0) return true;
  if (n === 0) return false;
  if (arr[n - 1] > sum) {
    return isSubsetSum(arr, n - 1, sum);
  }
  return isSubsetSum(arr, n - 1, sum) || isSubsetSum(arr, n - 1, sum [1] arr[n - 1]);
}

Drag options to blanks, or click blank then click option'

A/

B+

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction in the recursive call.

Not handling the base cases correctly.

We subtract the current element from sum to check if the remaining sum can be formed.

2fill in blank

medium

Complete the code to find the maximum number of activities that can be selected using a greedy approach.

DSA Javascript

function maxActivities(start, finish) {
  let count = 1;
  let lastFinish = finish[0];
  for (let i = 1; i < finish.length; i++) {
    if (start[i] [1] lastFinish) {
      count++;
      lastFinish = finish[i];
    }
  }
  return count;
}

Drag options to blanks, or click blank then click option'

A<

B<=

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= instead of < causes overlapping activities to be selected.

Using > or >= reverses the logic.

We select the next activity only if it starts after the last selected activity finishes.

3fill in blank

hard

Fix the error in the backtracking function to generate all subsets of an array.

DSA Javascript

function generateSubsets(arr, index, current, result) {
  if (index === arr.length) {
    result.push(current.slice());
    return;
  }
  generateSubsets(arr, index + 1, current, result);
  current.push(arr[index]);
  generateSubsets(arr, index + 1, current, result);
  current.[1]();
}

Drag options to blanks, or click blank then click option'

Ashift

Bpop

Cpush

Dunshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using push instead of pop causes infinite recursion.

Using shift or unshift removes elements from the wrong end.

We remove the last added element to backtrack and explore other subsets.

4fill in blank

hard

Fill both blanks to implement a backtracking solution for the N-Queens problem.

DSA Javascript

function isSafe(board, row, col, n) {
  for (let i = 0; i < col; i++) {
    if (board[row][i] === 1) return false;
  }
  for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j] === 1) return false;
  }
  for (let i = row, j = col; i < n && j >= 0; i++, j--) {
    if (board[i][j] === 1) return false;
  }
  return true;
}

function solveNQueens(board, col, n) {
  if (col === n) return true;
  for (let i = 0; i < n; i++) {
    if (isSafe(board, i, col, n)) {
      board[i][col] = 1;
      if (solveNQueens(board, col [1] 1, n)) return true;
      board[i][col] = [2];
    }
  }
  return false;
}

Drag options to blanks, or click blank then click option'

A+

B-

C0

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition for column increment.

Setting the board cell to null instead of 0.

We move to the next column by adding 1, and reset the board cell to 0 when backtracking.

5fill in blank

hard

Fill all three blanks to implement a greedy algorithm for the fractional knapsack problem.

DSA Javascript

function fractionalKnapsack(values, weights, capacity) {
  let n = values.length;
  let ratio = [];
  for (let i = 0; i < n; i++) {
    ratio.push({ index: i, value: values[i] [1] weights[i] });
  }
  ratio.sort((a, b) => b.value - a.value);
  let totalValue = 0;
  for (let i = 0; i < n; i++) {
    let idx = ratio[i].index;
    if (weights[idx] <= capacity) {
      capacity -= weights[idx];
      totalValue += values[idx];
    } else {
      totalValue += values[idx] [2] capacity [3] weights[idx];
      break;
    }
  }
  return totalValue;
}

Drag options to blanks, or click blank then click option'

A/

B*

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication instead of division for ratio.

Using addition or subtraction instead of multiplication for fractional value.

We calculate value-to-weight ratio by division, multiply fraction of capacity by value, and divide capacity by weight for fraction.

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