Why Backtracking and What Greedy Cannot Solve in DSA Rust - Why This Pattern

Mental Model

Backtracking tries all possible choices step-by-step to find the right answer, while greedy picks the best choice now but might miss the best overall.

Analogy: Imagine choosing dishes for a meal: greedy picks the tastiest dish first but might miss a better combination, backtracking tries all combos to find the tastiest meal.

Start
 ↓
Choice 1 -> Choice 2 -> Choice 3 -> ...
 ↓       ↓       ↓
Try all paths to find best

Dry Run Walkthrough

Input: Set: {1, 2, 3}, target sum: 4; find subset that sums to target

Goal: Find if any subset sums exactly to 4 using backtracking, showing why greedy fails

Step 1: Pick 3 (greedy picks largest first, 3)

Chosen: [3], Remaining: [1, 2]

Why: Greedy picks 3 first as largest, but 3 alone is less than 4

Step 2: Try adding 2 to 3 (greedy continues largest)

Chosen: [3, 2], sum=5 > 4, backtrack

Why: Sum exceeded target, so backtrack to try other options

Step 3: Backtrack: remove 2, try adding 1 to 3

Chosen: [3, 1], sum=4 == target, success

Why: Found subset that sums to target, backtracking found solution greedy missed

Result:

Chosen subset: 3 -> 1 -> null sums to 4

Annotated Code

DSA Rust

struct Solution;

impl Solution {
    fn backtrack(nums: &[i32], target: i32, start: usize, current_sum: i32, path: &mut Vec<i32>) -> bool {
        if current_sum == target {
            return true; // found valid subset
        }
        if current_sum > target || start == nums.len() {
            return false; // exceeded sum or no more elements
        }
        for i in start..nums.len() {
            path.push(nums[i]); // choose element
            if Self::backtrack(nums, target, i + 1, current_sum + nums[i], path) {
                return true; // propagate success
            }
            path.pop(); // backtrack
        }
        false
    }

    fn find_subset(nums: Vec<i32>, target: i32) -> Option<Vec<i32>> {
        let mut path = Vec::new();
        if Self::backtrack(&nums, target, 0, 0, &mut path) {
            Some(path)
        } else {
            None
        }
    }
}

fn main() {
    let nums = vec![3, 2, 1];
    let target = 4;
    match Solution::find_subset(nums, target) {
        Some(subset) => {
            for num in subset.iter() {
                print!("{} -> ", num);
            }
            println!("null");
        }
        None => println!("No subset found"),
    }
}

if current_sum == target { return true; }

Check if current subset sums to target, success condition

if current_sum > target || start == nums.len() { return false; }

Stop exploring if sum exceeded or no elements left

for i in start..nums.len() {

Try each remaining element as next choice

path.push(nums[i]);

Add current element to subset path

if Self::backtrack(nums, target, i + 1, current_sum + nums[i], path) { return true; }

Recurse with updated sum and next start index, propagate success

path.pop();

Remove last element to backtrack and try other options

Output

3 -> 1 -> null

Complexity Analysis

Time: O(2^n) because backtracking explores all subsets in worst case

Space: O(n) for recursion stack and path storage

vs Alternative: Greedy is O(n) but can fail to find correct subset; backtracking is slower but guaranteed to find solution if exists

Edge Cases

Empty set

Returns no subset found

DSA Rust

if current_sum > target || start == nums.len() { return false; }

Target zero

Returns empty subset immediately

DSA Rust

if current_sum == target { return true; }

No subset sums to target

Returns None after exploring all subsets

DSA Rust

for i in start..nums.len() { ... }

When to Use This Pattern

When a problem requires trying all combinations or subsets to find a solution and greedy choices fail, use backtracking to explore all possibilities.

Common Mistakes

Mistake: Stopping at first greedy choice without exploring alternatives
Fix: Implement backtracking to try all options and backtrack on failure

Summary

Backtracking tries all possible choices step-by-step to find a correct solution.

Use backtracking when greedy choices can miss the correct answer due to local decisions.

The key insight is that greedy picks locally best choices but backtracking explores all paths to find the global best.

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