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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Subset Sum Check

What is the output of this Rust code that uses backtracking to check if a subset sums to a target?

DSA Rust

fn subset_sum(nums: &[i32], target: i32, index: usize) -> bool {
    if target == 0 {
        return true;
    }
    if index == nums.len() || target < 0 {
        return false;
    }
    subset_sum(nums, target - nums[index], index + 1) || subset_sum(nums, target, index + 1)
}

fn main() {
    let nums = [3, 34, 4, 12, 5, 2];
    let target = 9;
    if subset_sum(&nums, target, 0) {
        println!("Found a subset with sum {}", target);
    } else {
        println!("No subset with sum {}", target);
    }
}

A Runtime error due to index out of bounds

B No subset with sum 9

C Compilation error due to missing return

D Found a subset with sum 9

💡 Hint

Think about whether any combination of numbers can add up to 9.

The function tries all subsets recursively. The subset {4, 5} sums to 9, so it returns true and prints the success message.

🧠 Conceptual

intermediate

Why Greedy Fails for Subset Sum

Why does a greedy algorithm fail to solve the subset sum problem correctly in all cases?

A Because greedy algorithms require sorted input, and subset sum is unsorted

B Because greedy always picks the largest number first, which may skip valid smaller subsets

C Because greedy algorithms cannot handle negative numbers

D Because greedy algorithms only work for problems with unique solutions

💡 Hint

Think about how greedy chooses elements and what it might miss.

Greedy picks the largest number first, which can cause it to miss smaller numbers that together form the target sum. Subset sum requires exploring all combinations, which greedy does not do.

❓ Predict Output

advanced

Output of Greedy Coin Change on Non-Canonical Set

What is the output of this Rust code using a greedy algorithm to make change with coins [1, 3, 4] for amount 6?

DSA Rust

fn greedy_coin_change(coins: &[i32], amount: i32) -> i32 {
    let mut remaining = amount;
    let mut count = 0;
    for &coin in coins.iter().rev() {
        count += remaining / coin;
        remaining %= coin;
    }
    count
}

fn main() {
    let coins = [1, 3, 4];
    let amount = 6;
    let result = greedy_coin_change(&coins, amount);
    println!("Coins used: {}", result);
}

A Coins used: 3

B Coins used: 2

C Coins used: 4

D Coins used: 1

💡 Hint

Check how greedy picks coins starting from largest to smallest.

Greedy picks one 4-coin, then two 1-coins, total 3 coins. But optimal is two 3-coins (2 coins). Greedy fails here.

🧠 Conceptual

advanced

Backtracking Advantage Over Greedy

Which statement best explains why backtracking can solve problems greedy cannot?

A Backtracking explores all possible solutions by trying every option, while greedy makes local optimal choices only

B Backtracking uses dynamic programming internally, greedy does not

C Backtracking always runs faster than greedy algorithms

D Backtracking only works on sorted data, greedy does not

💡 Hint

Think about how backtracking tries options compared to greedy.

Backtracking tries every possible choice and backtracks if it fails, ensuring all solutions are considered. Greedy picks the best local option and never revisits choices.

❓ Predict Output

expert

Output of Backtracking N-Queens Solution Count

What is the output of this Rust code that counts solutions to the 4-queens problem using backtracking?

DSA Rust

fn is_safe(board: &[usize], row: usize, col: usize) -> bool {
    for i in 0..row {
        if board[i] == col || (board[i] as isize - col as isize).abs() == (row as isize - i as isize).abs() {
            return false;
        }
    }
    true
}

fn solve_n_queens(n: usize, row: usize, board: &mut Vec<usize>, count: &mut usize) {
    if row == n {
        *count += 1;
        return;
    }
    for col in 0..n {
        if is_safe(board, row, col) {
            board[row] = col;
            solve_n_queens(n, row + 1, board, count);
        }
    }
}

fn main() {
    let n = 4;
    let mut board = vec![0; n];
    let mut count = 0;
    solve_n_queens(n, 0, &mut board, &mut count);
    println!("Number of solutions: {}", count);
}

A Number of solutions: 0

B Number of solutions: 4

C Number of solutions: 2

D Number of solutions: 1

💡 Hint

Recall the known number of solutions for 4-queens problem.

The 4-queens problem has exactly 2 distinct solutions. The code counts all valid placements using backtracking.

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