Why Backtracking and What Greedy Cannot Solve in DSA Rust - 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 cost to invite, and you have a limited budget. You want to invite the maximum number of friends without exceeding your budget.Sometimes, choosing the cheapest friends first (greedy) might not give the best result. You need to try different combinations to find the best group.

🎯 Goal: Build a simple Rust program that tries all combinations of friends to find the maximum number of friends you can invite within your budget using backtracking. This will show why greedy approach may fail and backtracking is needed.

📋 What You'll Learn

Create a dictionary of friends with their invitation costs

Set a budget limit

Use backtracking to find the maximum number of friends invited without exceeding budget

Print the maximum number of friends that can be invited

💡 Why This Matters

🌍 Real World

Backtracking is used in scheduling, puzzle solving, and decision making where all options must be explored.

💼 Career

Understanding backtracking helps in interviews and real-world problems like resource allocation and optimization.

1

Create the friends cost dictionary

Create a dictionary called friends with these exact entries: "Alice": 20, "Bob": 10, "Charlie": 15, "Diana": 25, "Eve": 30

DSA Rust

# Create the friends dictionary with their invitation costs
# Your code here

Hint

Use HashMap::new() and insert method to add friends and their costs.

2

Set the budget limit

Add a variable called budget and set it to 50 inside the main function after the friends dictionary

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut friends = HashMap::new();
    friends.insert("Alice", 20);
    friends.insert("Bob", 10);
    friends.insert("Charlie", 15);
    friends.insert("Diana", 25);
    friends.insert("Eve", 30);
    
    // Set the budget limit
    // Your code here
}

Hint

Just create a variable budget and assign 50.

3

Implement backtracking to find max friends

Write a function called max_friends that takes friends as a vector of costs, index as current position, budget as remaining budget, and returns the maximum number of friends that can be invited. Use recursion and backtracking to try including or excluding each friend. Call this function inside main with the costs vector, 0 as index, and budget. Store the result in a variable called result

DSA Rust

use std::collections::HashMap;

fn max_friends(friends: &Vec, index: usize, budget: i32) -> i32 {
    // Your code here
}

fn main() {
    let mut friends = HashMap::new();
    friends.insert("Alice", 20);
    friends.insert("Bob", 10);
    friends.insert("Charlie", 15);
    friends.insert("Diana", 25);
    friends.insert("Eve", 30);
    
    let budget = 50;

    // Your code here
}

Hint

Use recursion to try including or excluding each friend. Return the max count.

4

Print the maximum number of friends invited

Add a println! statement to print the text "Maximum friends invited: " followed by the value of result inside the main function

DSA Rust

use std::collections::HashMap;

fn max_friends(friends: &Vec, index: usize, budget: i32) -> i32 {
    if index == friends.len() {
        return 0;
    }
    let cost = friends[index];
    let mut include = 0;
    if cost  exclude { include } else { exclude }
}

fn main() {
    let mut friends = HashMap::new();
    friends.insert("Alice", 20);
    friends.insert("Bob", 10);
    friends.insert("Charlie", 15);
    friends.insert("Diana", 25);
    friends.insert("Eve", 30);
    
    let budget = 50;

    let costs: Vec = friends.values().cloned().collect();
    let result = max_friends(&costs, 0, budget);

    // Print the result
    // Your code here
}

Hint

Use println!("Maximum friends invited: {}", result); to show the answer.

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 backtrack when a choice leads to failure

B. Because greedy algorithms always find the best solution quickly

C. Because backtracking uses less memory than greedy algorithms

D. Because greedy algorithms are easier to implement

Solution

1. Step 1: Understand the problem nature

   The N-Queens puzzle requires placing queens so none attack each other, needing exploration of many configurations.

2. Step 2: Compare algorithm approaches

   Backtracking tries all possibilities and undoes wrong choices, while greedy picks local best without reconsidering.

3. Final Answer:

   Because backtracking explores all possible solutions and can backtrack when a choice leads to failure -> Option A

4. Quick Check:

   Backtracking = explores all options [OK]

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

Common Mistakes:

• Thinking greedy always finds the best solution
• Confusing memory use between algorithms
• Assuming backtracking is always slower

2. Which of the following is the correct Rust syntax to start a backtracking function that tries to fill a vector with numbers from 1 to n?

easy

A. fn backtrack(nums: &mut Vec<i32>, n: &i32) { ... }

B. fn backtrack(nums: Vec<i32>, n: i32) -> Vec<i32> { ... }

C. fn backtrack(nums: &Vec<i32>, n: i32) { ... }

D. fn backtrack(nums: &mut Vec<i32>, n: i32) { ... }

Solution

1. Step 1: Identify mutable reference usage

   Backtracking modifies the vector, so it needs a mutable reference: &mut Vec<i32>.

2. Step 2: Check parameter types

   Parameter n is passed by value (i32), not reference, for simplicity.

3. Final Answer:

   fn backtrack(nums: &mut Vec<i32>, n: i32) { ... } -> Option D

4. Quick Check:

   Mutable reference for vector = fn backtrack(nums: &mut Vec<i32>, n: i32) { ... } [OK]

Hint: Use &mut for vectors you want to change inside functions [OK]

Common Mistakes:

• Using &Vec<i32> which is immutable
• Passing n as &i32 unnecessarily
• Returning Vec<i32> when not needed

3. Consider this Rust code snippet for a backtracking function that tries to find subsets summing to a target. What will be printed?

fn backtrack(nums: &[i32], target: i32, start: usize, current: &mut Vec<i32>) {
    if target == 0 {
        println!("{:?}", current);
        return;
    }
    for i in start..nums.len() {
        if nums[i] > target {
            continue;
        }
        current.push(nums[i]);
        backtrack(nums, target - nums[i], i + 1, current);
        current.pop();
    }
}

fn main() {
    let nums = [2, 3, 6, 7];
    let mut current = Vec::new();
    backtrack(&nums, 7, 0, &mut current);
}

medium

A. [[7], [2, 3, 2]]

B. [[7], [2, 3]]

C. [[7]]

D. [[2, 3, 6]]

Solution

1. Step 1: Analyze the backtracking logic

   The function tries subsets of nums that sum to 7, moving forward each time (i + 1), so no repeats.

2. Step 2: Trace possible subsets

   Possible subsets: [7] sums to 7; [2,3] sums to 5; [2,3,6] exceeds; no repeats allowed, so only [7] matches exactly.

3. Final Answer:

   [[7]] -> Option C

4. Quick Check:

   Only subset summing to 7 without repeats = [7] [OK]

Hint: Check if indices move forward to avoid duplicates [OK]

Common Mistakes:

• Assuming repeated elements allowed
• Ignoring the target check
• Thinking [2,3,2] is valid subset

4. The following Rust backtracking code is intended to find all permutations of a vector of integers. What is the bug?

fn permute(nums: &mut Vec<i32>, start: usize) {
    if start == nums.len() {
        println!("{:?}", nums);
        return;
    }
    for i in start..nums.len() {
        nums.swap(start, i);
        permute(nums, start + 1);
    }
}

medium

A. Missing swap to revert the change after recursive call

B. Incorrect base case condition

C. Using &mut Vec<i32> instead of &Vec<i32>

D. Loop range should be 0..nums.len()

Solution

1. Step 1: Understand permutation generation

   Permutations require swapping elements and then swapping back to restore original order after recursion.

2. Step 2: Identify missing swap back

   The code swaps elements before recursion but never swaps back after, causing incorrect permutations.

3. Final Answer:

   Missing swap to revert the change after recursive call -> Option A

4. Quick Check:

   Swap back after recursion needed [OK]

Hint: Always undo swaps after recursive calls in permutations [OK]

Common Mistakes:

• Forgetting to swap back
• Changing base case incorrectly
• Using immutable references

5. You want to solve the classic "Subset Sum" problem: given a set of positive integers and a target sum, find if any subset sums exactly to the target. Why can't a greedy algorithm always solve this, and how does backtracking help? Choose the best explanation.

hard

A. Greedy always finds the smallest subset; backtracking finds the largest subset

B. Greedy picks largest numbers first which may overshoot; backtracking tries all combinations to find exact match

C. Greedy sorts the list; backtracking sorts and reverses it

D. Greedy uses recursion; backtracking uses iteration

Solution

1. Step 1: Understand greedy limitations

   Greedy algorithms pick the best immediate choice, like largest numbers, which can overshoot the target and miss valid subsets.

2. Step 2: Understand backtracking advantage

   Backtracking tries all possible subsets by exploring and undoing choices, ensuring it finds an exact match if one exists.

3. Final Answer:

   Greedy picks largest numbers first which may overshoot; backtracking tries all combinations to find exact match -> Option B

4. Quick Check:

   Greedy overshoot; backtracking explores all [OK]

Hint: Greedy picks local best; backtracking tries all combos [OK]

Common Mistakes:

• Thinking greedy always finds exact subset
• Confusing subset size with sum
• Mixing recursion and iteration definitions