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

Why Backtracking and What Greedy Cannot Solve

📖 Scenario: Imagine you are organizing a small party and want to invite friends. Each friend has a different availability and preference for attending. You want to find all possible groups of friends who can come together without conflicts.This is a simple example to understand why some problems need careful checking of all possibilities (backtracking) instead of just picking the best option at each step (greedy).

🎯 Goal: Build a program that tries all possible groups of friends to find those who can attend together without conflicts. This will show why backtracking is needed and why greedy methods may fail.

📋 What You'll Learn

Create a dictionary of friends with their availability status

Set a maximum group size limit

Use backtracking to find all valid groups of friends

Print all valid groups found

💡 Why This Matters

🌍 Real World

Backtracking helps in scheduling, puzzle solving, and finding all possible solutions when choices depend on previous selections.

💼 Career

Understanding backtracking is important for roles in software development, especially in algorithm design, game development, and optimization problems.

1

Create the friends availability dictionary

Create a dictionary called friends with these exact entries: 'Alice': true, 'Bob': false, 'Charlie': true, 'Diana': true, 'Evan': false

DSA Javascript

# Your code here

Hint

Use an object literal with friend names as keys and boolean values for availability.

2

Set the maximum group size

Create a variable called maxGroupSize and set it to 2

DSA Javascript

const friends = {
  'Alice': true,
  'Bob': false,
  'Charlie': true,
  'Diana': true,
  'Evan': false
};
# Your code here

Hint

Just create a constant variable with the number 2.

3

Write the backtracking function to find valid groups

Write a function called findGroups that takes currentGroup (array) and startIndex (number). Use backtracking to add friends who are available and find all groups up to maxGroupSize. Store valid groups in an array called validGroups. Use the friend names from Object.keys(friends) and check availability with friends[name].

DSA Javascript

const friends = {
  'Alice': true,
  'Bob': false,
  'Charlie': true,
  'Diana': true,
  'Evan': false
};

const maxGroupSize = 2;

const validGroups = [];

// Write the findGroups function below
# Your code here

Hint

Use recursion to try adding each available friend starting from startIndex. Add copies of current groups to validGroups.

4

Run the backtracking and print all valid groups

Call findGroups with an empty array and 0 as arguments. Then print validGroups using console.log(validGroups).

DSA Javascript

const friends = {
  'Alice': true,
  'Bob': false,
  'Charlie': true,
  'Diana': true,
  'Evan': false
};

const maxGroupSize = 2;

const validGroups = [];

function findGroups(currentGroup, startIndex) {
  if (currentGroup.length > 0) {
    validGroups.push([...currentGroup]);
  }
  if (currentGroup.length === maxGroupSize) {
    return;
  }

  const friendNames = Object.keys(friends);

  for (let i = startIndex; i < friendNames.length; i++) {
    const name = friendNames[i];
    if (friends[name]) {
      currentGroup.push(name);
      findGroups(currentGroup, i + 1);
      currentGroup.pop();
    }
  }
}

// Call findGroups and print validGroups
# Your code here

Hint

Start with an empty group and index 0. Then print the array of valid groups.

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