Why Backtracking and What Greedy Cannot Solve in DSA Rust - Quick Recap

Recall & Review

beginner

What is the main idea behind backtracking?

Backtracking tries all possible options step-by-step and goes back (undoes) when a choice leads to a dead end, ensuring all solutions are explored.

beginner

Why can't greedy algorithms solve all problems?

Greedy algorithms make the best choice at each step without looking ahead, which can miss the overall best solution in problems needing global decisions.

intermediate

Give an example problem where greedy fails but backtracking works.

The classic example is the 'Subset Sum' problem: greedy picks large numbers first but may miss a combination that sums exactly to target; backtracking tries all subsets.

intermediate

How does backtracking differ from brute force?

Backtracking is a smarter brute force that stops exploring a path early if it can't lead to a solution, saving time compared to checking all possibilities blindly.

beginner

What kind of problems are best suited for backtracking?

Problems with many possible combinations or arrangements where you need to find all or some solutions, like puzzles, permutations, and constraint satisfaction problems.

Why does greedy fail in some problems?

A It only looks at the current best choice without considering future consequences

B It tries all possible solutions

C It always finds the global optimum

D It uses backtracking to undo choices

Greedy algorithms pick the best immediate option but may miss better solutions that require planning ahead.

What does backtracking do when it hits a dead end?

A Goes back to previous step and tries a different option

B Stops the entire process

C Chooses the next best greedy option

D Returns the first solution found

Backtracking reverses the last choice to explore other possibilities.

Which problem is a classic example where backtracking is needed?

A Sorting numbers

B Finding maximum in array

C Subset Sum problem

D Simple addition

Subset Sum requires checking many combinations, which backtracking handles well.

How does backtracking improve over brute force?

A By trying only one solution

B By stopping early when no solution is possible on a path

C By always choosing the largest number

D By sorting inputs first

Backtracking prunes paths that cannot lead to a solution, saving time.

Which type of problems is NOT ideal for greedy algorithms?

A Problems with local optimal choices leading to global optimum

B Problems with sorted inputs

C Problems with simple maximum or minimum search

D Problems requiring global planning and combinations

Greedy fails when the best local choice doesn't lead to the best overall solution.

Explain why backtracking is necessary when greedy algorithms fail. Include an example.

Think about problems where you must try many combinations.

Describe how backtracking works step-by-step and how it differs from brute force.

Focus on the undo and pruning steps.

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