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

Why Backtracking and What Greedy Cannot Solve

📖 Scenario: Imagine you are organizing a small party and want to invite friends with different preferences. You want to find all possible groups of friends that fit a certain budget. Sometimes, picking the cheapest friends first (greedy) won't find the best group. You need to try different combinations carefully (backtracking).

🎯 Goal: You will create a program that tries all possible groups of friends within a budget using backtracking. You will see why a simple greedy approach cannot always find all valid groups.

📋 What You'll Learn

Create a list of friends with their costs

Set a budget limit

Use backtracking to find all groups of friends within the budget

Print all valid groups

💡 Why This Matters

🌍 Real World

Backtracking helps in planning events, scheduling, and solving puzzles where all combinations matter.

💼 Career

Understanding backtracking is key for roles in software development, especially in algorithm design, optimization, and problem solving.

1

Create the list of friends with their costs

Create a constant array called friends with these exact entries: { name: 'Alice', cost: 20 }, { name: 'Bob', cost: 10 }, { name: 'Charlie', cost: 15 }, { name: 'Diana', cost: 25 }

DSA Typescript

// Your code here

Hint

Use an array of objects with name and cost properties.

2

Set the budget limit

Create a constant called budget and set it to 35

DSA Typescript

const friends = [
  { name: 'Alice', cost: 20 },
  { name: 'Bob', cost: 10 },
  { name: 'Charlie', cost: 15 },
  { name: 'Diana', cost: 25 }
];
// Your code here

Hint

Just create a number variable called budget with value 35.

3

Write the backtracking function to find all groups within budget

Write a function called findGroups that takes index, currentGroup, and currentCost as parameters. Use backtracking to explore all friend combinations starting from index. If currentCost is less than or equal to budget and currentGroup is not empty, add the currentGroup to a global array validGroups. Recursively try adding each friend from index onwards. Do not exceed the budget.

DSA Typescript

const friends = [
  { name: 'Alice', cost: 20 },
  { name: 'Bob', cost: 10 },
  { name: 'Charlie', cost: 15 },
  { name: 'Diana', cost: 25 }
];

const budget = 35;

const validGroups: string[][] = [];

// Your code here

Hint

Use recursion and try adding each friend if budget allows. Save copies of valid groups.

4

Call the function and print all valid groups

Call findGroups starting from index 0, empty array [], and cost 0. Then print the validGroups array.

DSA Typescript

const friends = [
  { name: 'Alice', cost: 20 },
  { name: 'Bob', cost: 10 },
  { name: 'Charlie', cost: 15 },
  { name: 'Diana', cost: 25 }
];

const budget = 35;

const validGroups: string[][] = [];

function findGroups(index: number, currentGroup: string[], currentCost: number): void {
  if (currentCost  0) {
    validGroups.push([...currentGroup]);
  }

  for (let i = index; i < friends.length; i++) {
    const friend = friends[i];
    if (currentCost + friend.cost <= budget) {
      currentGroup.push(friend.name);
      findGroups(i + 1, currentGroup, currentCost + friend.cost);
      currentGroup.pop();
    }
  }
}

// Your code here

Hint

Start the search from 0 with empty group and cost 0. Then print the results.