Backtracking Concept and Decision Tree Visualization in DSA Rust

Mental Model

Backtracking tries choices one by one and goes back if a choice leads to a dead end.

Analogy: Imagine walking through a maze and marking your path. If you hit a wall, you return to the last fork and try a different path.

Start
  ↓
Choice 1 -> Dead end
  ↑
Choice 2 -> Continue -> Goal

Dry Run Walkthrough

Input: Find all subsets of [1, 2] using backtracking

Goal: List all possible subsets by choosing or skipping each element

Step 1: Start with empty subset []

[] ↑ (at index 0)

Why: We begin with no elements chosen

Step 2: Choose element 1, subset becomes [1]

[1] ↑ (at index 1)

Why: Try including first element

Step 3: Choose element 2, subset becomes [1, 2]

[1, 2] ↑ (at index 2 end)

Why: Try including second element

Step 4: Reached end, record subset [1, 2]

[1, 2]

Why: One complete subset found

Step 5: Backtrack: remove 2, subset back to [1]

[1] ↑ (at index 1)

Why: Try skipping second element

Step 6: Skip element 2, subset remains [1]

[1]

Why: Record subset without second element

Step 7: Backtrack: remove 1, subset back to []

[] ↑ (at index 0)

Why: Try skipping first element

Step 8: Skip element 1, subset remains []

[] ↑ (at index 1)

Why: Try including or skipping second element without first

Step 9: Choose element 2, subset becomes [2]

[2] ↑ (at index 2 end)

Why: Include second element only

Step 10: Reached end, record subset [2]

[2]

Why: Another complete subset found

Step 11: Backtrack: remove 2, subset back to []

[]

Why: Try skipping second element as well

Step 12: Skip element 2, subset remains []

[]

Why: Record empty subset

Result:

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

Annotated Code

DSA Rust

fn backtrack(nums: &[i32], index: usize, current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if index == nums.len() {
        result.push(current.clone()); // record current subset
        return;
    }
    // Choose nums[index]
    current.push(nums[index]);
    backtrack(nums, index + 1, current, result); // move forward
    current.pop(); // backtrack: remove last choice
    // Skip nums[index]
    backtrack(nums, index + 1, current, result); // move forward without choice
}

fn main() {
    let nums = vec![1, 2];
    let mut result = Vec::new();
    let mut current = Vec::new();
    backtrack(&nums, 0, &mut current, &mut result);
    for subset in result {
        println!("{:?}", subset);
    }
}

if index == nums.len() {

Check if we reached the end of the list to record a subset

result.push(current.clone()); // record current subset

Save the current subset as one valid answer

current.push(nums[index]);

Choose current element to include in subset

backtrack(nums, index + 1, current, result); // move forward

Explore further choices with current element included

current.pop(); // backtrack: remove last choice

Undo choice to try skipping current element

backtrack(nums, index + 1, current, result); // move forward without choice

Explore further choices without current element

Output

[]

[1]

[1, 2]

[2]

Complexity Analysis

Time: O(2^n) because each element can be either chosen or skipped, doubling possibilities

Space: O(n) for recursion stack and current subset storage at each step

vs Alternative: Compared to iterative methods, backtracking cleanly explores all subsets without extra bookkeeping

Edge Cases

Empty input list

Returns one subset: the empty subset []

DSA Rust

if index == nums.len() {

Single element list

Returns two subsets: [] and [element]

DSA Rust

if index == nums.len() {

When to Use This Pattern

When you need to explore all possible choices and undo decisions to try alternatives, use backtracking to systematically search all options.

Common Mistakes

Mistake: Not undoing the choice after recursive call, causing wrong subsets
Fix: Always remove the last chosen element (pop) before trying the next option

Mistake: Not checking the base case to stop recursion
Fix: Add a condition to record the current subset when reaching the end

Summary

Backtracking tries all choices by picking or skipping elements and undoing picks to explore alternatives.

Use it when you want to find all possible combinations, subsets, or paths.

The key is to make a choice, explore deeper, then undo that choice to try others.

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