Backtracking Concept and Decision Tree Visualization in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Path Exploration

What is the printed output of the following Rust backtracking code that explores all subsets of [1, 2]?

DSA Rust

fn backtrack(path: &mut Vec<i32>, nums: &[i32], index: usize) {
    if index == nums.len() {
        println!("{:?}", path);
        return;
    }
    // Include nums[index]
    path.push(nums[index]);
    backtrack(path, nums, index + 1);
    // Exclude nums[index]
    path.pop();
    backtrack(path, nums, index + 1);
}

fn main() {
    let nums = vec![1, 2];
    let mut path = Vec::new();
    backtrack(&mut path, &nums, 0);
}

A [[1, 2], [1], [2], []]

B [[1, 2], [1], [], [2]]

C [[], [1], [2], [1, 2]]

D [[2, 1], [2], [1], []]

💡 Hint

Think about how the function includes or excludes each number step by step.

The function explores all subsets by choosing to include or exclude each element in order. The order of printing is: include 1 then include 2, include 1 then exclude 2, exclude 1 then include 2, exclude 1 then exclude 2.

🧠 Conceptual

intermediate

Number of Nodes in Backtracking Decision Tree

For a backtracking algorithm that makes two choices at each step for n steps, how many total nodes are in the decision tree?

A n^2

B 2^n

C n!

D 2*n

💡 Hint

Each step doubles the number of paths.

At each step, the algorithm branches into 2 choices, so total nodes are 2 multiplied by itself n times, which is 2^n.

🔧 Debug

advanced

Identify the Backtracking Bug in Rust Code

What error or issue does the following Rust backtracking code have when generating permutations of [1, 2, 3]? fn backtrack(nums: &mut Vec, start: usize) { if start == nums.len() { println!("{:?}", nums); return; } for i in start..nums.len() { nums.swap(start, i); backtrack(nums, start + 1); // Missing swap back here } } fn main() { let mut nums = vec![1, 2, 3]; backtrack(&mut nums, 0); }

A The code prints duplicate permutations because it does not swap back after recursion.

B The code prints no output because the base case is never reached.

C The code does not compile because of mutable borrow errors.

D The code causes a runtime panic due to out-of-bounds indexing.

💡 Hint

Check if the state is restored after recursive calls.

The code swaps elements to generate permutations but forgets to swap them back after the recursive call. This causes the vector to remain changed, leading to duplicate or incorrect permutations.

🚀 Application

advanced

Backtracking to Solve N-Queens: Number of Solutions for N=4

Using backtracking to solve the 4-Queens problem, how many distinct solutions are there?

A 8

B 4

C 2

D 1

💡 Hint

Try to visualize placing 4 queens so none attack each other.

The classic 4-Queens problem has exactly 2 distinct solutions where 4 queens can be placed on a 4x4 board without attacking each other.

🧠 Conceptual

expert

Backtracking Tree Pruning Impact on Complexity

How does pruning branches in a backtracking decision tree affect the algorithm's time complexity?

A Pruning increases the time complexity because it adds extra checks.

B Pruning has no effect on time complexity but reduces memory usage.

C Pruning changes the algorithm to a greedy approach, losing correctness.

D Pruning reduces the number of nodes explored, potentially lowering time complexity exponentially.

💡 Hint

Think about how skipping impossible paths affects total work.

Pruning cuts off branches that cannot lead to a solution early, so fewer nodes are explored. This can reduce the exponential time complexity significantly.

Practice

1. What is the main idea behind backtracking in algorithms?

easy

A. Store data in a tree structure for quick access

B. Sort data before processing it

C. Use loops to repeat actions a fixed number of times

D. Try all possible options and undo choices when they lead to dead ends

Solution

1. Step 1: Understand backtracking purpose

   Backtracking tries all options to find solutions by exploring choices step-by-step.

2. Step 2: Recognize undoing choices

   When a choice leads to no solution, backtracking reverses it to try others.

3. Final Answer:

   Try all possible options and undo choices when they lead to dead ends -> Option D

4. Quick Check:

   Backtracking = Try and undo [OK]

Hint: Backtracking means try, undo if fails, then try next [OK]

Common Mistakes:

• Confusing backtracking with sorting
• Thinking backtracking only uses loops
• Believing backtracking stores data only

2. Which of the following Rust code snippets correctly starts a backtracking function signature?

easy

A. fn backtrack(path: &mut Vec<i32>, choices: &[i32]) { ... }

B. fn backtrack(path: Vec<i32>, choices: Vec<i32>) -> i32 { ... }

C. fn backtrack(path: &Vec<i32>, choices: &Vec bool { ... }

D. fn backtrack(path: Vec<i32>, choices: &[i32]) -> String { ... }

Solution

1. Step 1: Identify mutable path parameter

   Backtracking usually modifies the current path, so it needs a mutable reference.

2. Step 2: Check choices parameter type

   Choices are usually passed as a slice reference for read-only access.

3. Final Answer:

   fn backtrack(path: &mut Vec<i32>, choices: &[i32]) { ... } -> Option A

4. Quick Check:

   Mutable path + slice choices = fn backtrack(path: &mut Vec<i32>, choices: &[i32]) { ... } [OK]

Hint: Use &mut for path to change it, &[i32] for choices [OK]

Common Mistakes:

• Passing path by value instead of mutable reference
• Returning wrong types for backtracking
• Using owned Vec for choices instead of slice

3. What will be the output of the following Rust backtracking code snippet that prints all subsets of [1, 2]?

fn backtrack(path: &mut Vec<i32>, nums: &[i32], index: usize) {
    if index == nums.len() {
        println!("{:?}", path);
        return;
    }
    // Include nums[index]
    path.push(nums[index]);
    backtrack(path, nums, index + 1);
    path.pop();
    // Exclude nums[index]
    backtrack(path, nums, index + 1);
}

fn main() {
    let mut path = Vec::new();
    let nums = [1, 2];
    backtrack(&mut path, &nums, 0);
}

medium

A. [1]
[2]
[1, 2]
[]

B. [1, 2]
[1]
[2]
[]

C. []
[1]
[2]
[1, 2]

D. [1, 2]
[2]
[1]
[]

Solution

1. Step 1: Trace recursive calls including and excluding elements

   The function first includes 1, then includes 2, prints [1, 2], then excludes 2, prints [1], then excludes 1 and includes 2, prints [2], finally excludes both and prints [].

2. Step 2: Order of printed subsets

   Due to include branch first in depth-first recursion: [1, 2]\n[1]\n[2]\n[].

3. Final Answer:

   [1, 2]\n[1]\n[2]\n[] -> Option B

4. Quick Check:

   Include first: [1,2] [1] [2] [] [OK]

Hint: Include branch first: [1,2] then [1] then [2] [] [OK]

Common Mistakes:

• Mixing order of subsets printed
• Forgetting to pop after push
• Confusing include/exclude steps

4. Identify the bug in this Rust backtracking snippet that tries to generate permutations of [1, 2]:

fn backtrack(path: &mut Vec<i32>, nums: &[i32], used: &mut Vec<bool>) {
    if path.len() == nums.len() {
        println!("{:?}", path);
        return;
    }
    for i in 0..nums.len() {
        if used[i] {
            continue;
        }
        path.push(nums[i]);
        // Missing used[i] = true;
        backtrack(path, nums, used);
        path.pop();
        used[i] = false;
    }
}

fn main() {
    let mut path = Vec::new();
    let nums = [1, 2];
    let mut used = vec![false; nums.len()];
    backtrack(&mut path, &nums, &mut used);
}

medium

A. The base case condition is incorrect

B. The path vector should not be mutable

C. The line setting used[i] = true is missing before recursion

D. The loop should iterate from 1 to nums.len()

Solution

1. Step 1: Check usage of 'used' vector

   The 'used' vector tracks which elements are included. It must be set to true before recursion to avoid reuse.

2. Step 2: Identify missing assignment

   Currently, used[i] is never set to true before recursion, so the same element can be reused multiple times incorrectly.

3. Final Answer:

   The line setting used[i] = true is missing before recursion -> Option C

4. Quick Check:

   Missing used[i] = true causes reuse error [OK]

Hint: Set used[i] = true before recursion, false after [OK]

Common Mistakes:

• Not marking elements as used before recursion
• Incorrect base case length check
• Loop index off-by-one errors

5. Given a decision tree for solving the N-Queens problem with backtracking, which of the following best describes the role of pruning in the tree?

hard

A. Pruning removes branches where queens attack each other, reducing search space

B. Pruning adds more branches to explore all possibilities

C. Pruning sorts the queens by their row positions

D. Pruning duplicates nodes to increase solution count

Solution

1. Step 1: Understand pruning in backtracking

   Pruning cuts off branches in the decision tree that cannot lead to valid solutions, saving time.

2. Step 2: Apply pruning to N-Queens

   In N-Queens, pruning removes branches where queens threaten each other, so no need to explore further.

3. Final Answer:

   Pruning removes branches where queens attack each other, reducing search space -> Option A

4. Quick Check:

   Pruning = cut invalid branches [OK]

Hint: Pruning cuts invalid paths early to save time [OK]

Common Mistakes:

• Thinking pruning adds branches
• Confusing pruning with sorting
• Believing pruning duplicates nodes