Why Backtracking and What Greedy Cannot Solve in DSA Rust - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a solution is valid in backtracking.

DSA Rust

fn is_valid(solution: &Vec<i32>, candidate: i32) -> bool {
    for &item in solution.iter() {
        if item == [1] {
            return false;
        }
    }
    true
}

Drag options to blanks, or click blank then click option'

Acandidate

Bsolution.len()

Citem

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing item with solution length instead of candidate.

Returning true inside the loop prematurely.

We check if the candidate is already in the solution to avoid duplicates.

2fill in blank

medium

Complete the code to backtrack by removing the last candidate.

DSA Rust

fn backtrack(solution: &mut Vec<i32>, candidates: &Vec<i32>) {
    if solution.len() == candidates.len() {
        println!("Solution: {:?}", solution);
        return;
    }
    for &candidate in candidates.iter() {
        if is_valid(solution, candidate) {
            solution.push(candidate);
            backtrack(solution, candidates);
            solution.[1]();
        }
    }
}

Drag options to blanks, or click blank then click option'

Apush

Bremove

Cclear

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using clear() which removes all elements.

Using remove() without index which causes error.

We use pop() to remove the last added candidate to try other options.

3fill in blank

hard

Fix the error in the greedy approach that fails to find the correct solution.

DSA Rust

fn greedy_select(weights: &Vec<i32>, values: &Vec<i32>, capacity: i32) -> i32 {
    let mut total_value = 0;
    let mut remaining = capacity;
    for i in 0..weights.len() {
        if weights[i] <= [1] {
            total_value += values[i];
            remaining -= weights[i];
        }
    }
    total_value
}

Drag options to blanks, or click blank then click option'

Aremaining

Bcapacity

Cweights[i]

Dvalues[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Checking weights[i] <= capacity always, ignoring remaining capacity.

Adding values without checking weight.

We must check if the current item's weight fits in the remaining capacity, not the original capacity.

4fill in blank

hard

Fill both blanks to implement backtracking for subset sum problem.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Atarget

Bindex

Cnums.len()

Dcurrent_sum

Attempts:

3 left

💡 Hint

Common Mistakes

Passing wrong arguments order.

Using target or current_sum as index.

We pass index + 1 and keep target and current_sum updated correctly in recursive calls.

5fill in blank

hard

Fill all three blanks to implement backtracking for generating permutations.

DSA Rust

fn permute(nums: &mut Vec<i32>, start: usize, result: &mut Vec<Vec<i32>>) {
    if start == nums.len() {
        result.push(nums.clone());
        return;
    }
    for i in start..nums.len() {
        nums.[1](start, i);
        permute(nums, [2], result);
        nums.[3](start, i);
    }
}

Drag options to blanks, or click blank then click option'

Aswap

Bstart + 1

Clen

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of swap.

Not incrementing start in recursive call.

We swap elements to generate permutations, recurse with start + 1, then swap back to restore order.

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