Step 2 of 6

Branching recursion and backtracking

When a function calls itself more than once, the calls branch out into a recursion tree. The classic example is Fibonacci: fib(n) = fib(n - 1) + fib(n - 2). Written directly, it's a beautiful one-liner and a terrible program. Count the calls:

fn fib(n: u32, calls: &mut u64) -> u64 {
    *calls += 1;
    if n < 2 {
        return n as u64;
    }
    fib(n - 1, calls) + fib(n - 2, calls)
}

fn main() {
    for n in [10, 20, 30] {
        let mut calls = 0;
        let value = fib(n, &mut calls);
        println!("fib({n}) = {value} after {calls} calls");
    }
}

fib(10) = 55 after 177 calls
fib(20) = 6765 after 21891 calls
fib(30) = 832040 after 2692537 calls

Each extra n multiplies the work by about 1.6: that's exponential, O(1.6ⁿ). fib(60) this way would take longer than you want to wait. The cause is that the same values are computed over and over (fib(28) is computed twice for fib(30), fib(27) three times...). The next step fixes that.

Backtracking: exploring every choice

Sometimes branching is the point: you really do want to try every combination of choices, like every set of toppings, every team, every move. Backtracking does it with one shared, growing "path":

1. choose: add an option to the path,
2. explore: recurse to make the remaining choices,
3. un-choose: remove it again, so the next branch starts clean.

fn explore<'a>(toppings: &[&'a str], i: usize, chosen: &mut Vec<&'a str>) {
    if i == toppings.len() {
        println!("{{{}}}", chosen.join(", "));
        return;
    }
    chosen.push(toppings[i]); // choose: take toppings[i]
    explore(toppings, i + 1, chosen); // explore with it
    chosen.pop(); // un-choose
    explore(toppings, i + 1, chosen); // explore without it
}

fn main() {
    explore(&["cheese", "olives", "basil"], 0, &mut Vec::new());
}

{cheese, olives, basil}
{cheese, olives}
{cheese, basil}
{cheese}
{olives, basil}
{olives}
{basil}
{}

Each item is either taken or not, so n items give 2ⁿ subsets: fine for 20 items (a million), hopeless for 60. The 'a lifetime says the chosen names borrow from the same place as toppings, so the path can hold &str without copying any strings.

Pruning makes backtracking practical: stop exploring a branch as soon as it can't lead to an answer (the budget is already exceeded, not enough items remain to fill a team). A pruned search can be thousands of times faster than the full tree.

Common mistakes

• Forgetting to un-choose. Without the pop(), later branches see leftovers from earlier ones.
• Copying the whole path at every step. Clone the path only when you record a finished answer.
• Branching recursion on big inputs. 2ⁿ or n! grows absurdly fast. If the same subproblems repeat, you need memoization (next step), not a faster computer.

Your task

A customer has gift cards with the given values and wants to spend exactly target. Write fn count_subsets_with_sum(cards: &[u32], target: u32) -> usize: the number of different sets of cards (each card used at most once; equal values on different cards count as different cards) whose values add up to exactly target. The empty set adds up to 0. Use recursion that, for each card, counts the ways with it and without it, and prune: never take a card bigger than what's left. The tests go up to 20 cards.

Challenge 2

The coach picks teams of exactly k players. Write fn team_options(players: &[&str], k: usize) -> Vec<String> that lists every team, each written as the names joined with + in the players' order, with the teams in order too: for ["ana", "ben", "cy"] and k = 2 that's ["ana+ben", "ana+cy", "ben+cy"]. k is at least 1; if it's bigger than the number of players, there are no teams.

Use backtracking with a Vec<&str> path: for each player from a start position, choose them, explore the rest, un-choose. Prune when there aren't enough players left to fill the team.

Challenge 3

The N-Queens puzzle, a backtracking classic: place n queens on an n by n chessboard so that no two attack each other (no two share a row, a column or a diagonal). Write fn n_queens(n: usize) -> usize that counts the solutions. There are 92 for the standard 8 by 8 board.

Place one queen per row, recursively. Keep three Vec<bool> of "taken" markers: columns (n), diagonals going one way (row + col, 2n of them) and the other way (row + n - 1 - col). For each column of the current row that is free on all three, mark, recurse into the next row, unmark. Reaching row n means you found a solution.

Previous: Recursion: a function that calls itself Next: Memoization with a HashMap