Backtracking: choose, explore, unchoose

Backtracking answers “list every …” and “find one … that satisfies” problems by building an answer one decision at a time. At each step it chooses an option, explores everything that can follow from it with a recursive call, and then unchooses it, putting the state back exactly as it was before it tries the next option. A partial answer that already breaks a rule is dropped on the spot, and with it every answer that would have grown from it. NIST’s Dictionary of Algorithms and Data Structures describes the result as a depth-first search of a tree of partial solutions, in which each choice is a node. Four decisions come before any code: the state (what has been decided), the choices (what may come next), the goal (when the state is an answer to record) and the constraints (when to give up early). This lesson writes the template, solves one problem in full in five languages, measures what undoing saves over copying, and sizes search trees before running them.

When a problem calls for backtracking

The statement usually gives it away:

• “List all”, “every way”, “all possible”, “generate every valid …”, where an answer is made of several decisions: subsets, orderings, groupings, assignments, paths through a grid.
• “Find any arrangement that satisfies …”, under rules that are easy to check on a partial arrangement but offer no shortcut: puzzles, timetables, placements on a board.
• Small inputs. Around 20 items when each one is in or out (2²⁰ is about a million), around 10 for orderings (10! is 3,628,800), or a promise that the answer itself is small.

Three neighbouring patterns look similar and want other tools:

• “How many ways” or “the best total”, when different choices lead to the same smaller problem: dynamic programming counts or optimises without listing anything, and later modules of this track build it. Listing a billion answers takes at least a billion steps, while a count can often be found in a few million.
• A choice that can be proved safe to make once and keep, such as taking the meeting that ends first: a greedy rule never needs to undo anything.
• The fewest moves or the shortest path through a space of states: breadth-first search finds it without trying every path.

The template: four names, three moves

Every backtracking function has the same skeleton. Here it is on a task small enough to check by hand: every code of three letters from A, B and C in which no letter comes twice in a row.

"""The backtracking template on a small task: every code of 3 letters from A, B and C with no letter twice in a row."""


def codes(letters, length):
    found = []
    code = []  # the state: the letters decided so far
    calls = 0

    def backtrack():
        nonlocal calls
        calls += 1
        if len(code) == length:  # goal: the code is complete
            found.append("".join(code))  # record a copy of the state, never the list itself
            return
        for letter in letters:  # choices: any letter for the next place
            if code and code[-1] == letter:  # constraint: not the letter just used
                continue
            code.append(letter)  # choose
            backtrack()  # explore everything that can follow
            code.pop()  # unchoose: the state is as it was before the choice

    backtrack()
    return found, calls


found, calls = codes("ABC", 3)
print(" ".join(found))
print(len(found), "codes from", calls, "calls; without the rule there would be", 3**3, "codes")

ABA ABC ACA ACB BAB BAC BCA BCB CAB CAC CBA CBC
12 codes from 22 calls; without the rule there would be 27 codes

Name the four parts for the task before you write the function:

1. State: what has been decided so far. Here it is code, the letters placed so far, one list that every call shares.
2. Choices: what may come next from this state. Here, any of the three letters for the next place.
3. Goal: when the state is a complete answer. Here, three letters placed. Record a copy, because the state itself will change again.
4. Constraints: when a choice cannot lead to an answer. Here, the letter just used. Skipping it at once also skips every code that would have started that way.

Then every choice that passes the constraints goes through the same three moves: choose changes the state (code.append(letter)), explore makes the recursive call that deals with everything that can follow, and unchoose puts the state back (code.pop()). The moves rely on one rule, the contract of a backtracking call: when a call returns, the state is exactly as it was when the call began. The contract lets every option of the loop start from the same state. It is proved like the contract of the lesson on recursive tree functions, by induction: a call that records an answer changes nothing, and any other call undoes each of its own changes once the deeper calls, which keep the contract, have returned.

The output shows 12 codes from 22 calls. The calls are the nodes of the search tree: one for the empty code, 3 with one letter, 6 with two and 12 with three, because the constraint leaves two options after the first letter. Counting nodes this way is how the last section of this lesson sizes a search before running it.

A problem solved in full: toppings within a budget

Three examples, which every version below prints:

1. Olives 40, paneer 70, corn 30 and onion 50 with a budget of 120 give 12 sets, from the plain pizza to olives, corn and onion at exactly 120. Four sets go over: olives, paneer and corn (140), olives, paneer and onion (160), paneer, corn and onion (150), and all four (190).
2. With a budget of 0, only the plain pizza fits.
3. Two toppings at 60 each with a budget of 100 give 3 sets: the plain pizza and each topping alone. Equal prices do not make two toppings the same one.

The brute force: every subset

Build each of the 2ⁿ subsets, add up its prices and keep it if the total fits. itertools.combinations produces the subsets of each size in lexicographic order, so the whole brute force is three lines and plainly correct:

"""The brute force: build every subset of the menu, then keep the ones within the budget."""
import time
from itertools import combinations


def topping_sets_brute(prices, budget):
    """Every set of toppings within budget, by trying all 2**n subsets (each as positions in menu order)."""
    n = len(prices)
    every_subset = (s for size in range(n + 1) for s in combinations(range(n), size))
    return [list(s) for s in every_subset if sum(prices[j] for j in s) <= budget]


if __name__ == "__main__":
    print(topping_sets_brute([40, 70, 30, 50], 120))
    big = [40 + (37 * i) % 81 for i in range(40)]  # the 40-topping menu, each priced from 40 to 120
    print(f"{'toppings':>8}  {'subsets tried':>13}  {'sets within 300':>15}  time")
    for n in (16, 18, 20):
        start = time.perf_counter()
        found = topping_sets_brute(big[:n], 300)
        seconds = time.perf_counter() - start
        print(f"{n:>8}  {2**n:>13,}  {len(found):>15,}  {seconds:.2f} s")
    # The work is about n * 2**n additions: from 20 to 40 toppings, 2**20 times as many subsets, each twice as long.
    days = seconds * 2**20 * 2 / 86400
    print(f"40 toppings: {2**40:,} subsets to try, about {days:.0f} days at the speed of the last row")

[[], [0], [1], [2], [3], [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3], [0, 2, 3]]
toppings  subsets tried  sets within 300  time
      16         65,536            1,383  0.03 s
      18        262,144            2,114  0.67 s
      20      1,048,576            3,246  2.39 s
40 toppings: 1,099,511,627,776 subsets to try, about 58 days at the speed of the last row

It makes a good reference to test against, and it cannot meet the limits. Each extra topping doubles the number of subsets and each subset costs up to n additions, so the work grows like n · 2ⁿ. The last line turns the time for 20 toppings into an estimate for 40, and the estimate comes out in days, because 40 toppings have 1,099,511,627,776 subsets. Nearly all of them are far over budget, and the brute force builds every one of them anyway.

What to notice

Prices are positive, so adding a topping never lowers the total. Once a partial set is over budget, every set that contains it is over budget too, and there is no reason to build any of them. A search that grows sets one topping at a time can test the budget at every step and abandon a branch the moment it fails. Its work then follows the number of sets that fit, which the limits promise is at most 100,000, instead of the 2⁴⁰ sets that exist.

Backtracking, step by step

The four names for this problem:

• State: chosen, the positions picked so far in menu order, with their total and start, the first position that may still be added. Because toppings are only ever added in menu order, each set is built in exactly one way.
• Choices: every position j from start to n − 1.
• Goal: here every state is an answer, because a set is checked against the budget before it is entered. So each call records a copy of chosen before it does anything else.
• Constraint: skip j when total + prices[j] is over the budget.

The steps:

1. Start with an empty chosen, with start and total both 0.
2. Record a copy of chosen.
3. For each j from start to n − 1, skip it when total + prices[j] > budget.
4. Otherwise append j (choose), call the function with start = j + 1 and the new total (explore), then remove j again (unchoose).
5. When the first call returns, the recorded sets are the answer.

Why it lists every set exactly once

Every set that fits is listed. Write its positions in increasing order, j₁ < j₂ < … < jₖ. The first call may choose j₁, the call that choice makes may choose j₂, and so on, because each position comes after the one before it and each prefix of the set costs no more than the whole set, so the constraint skips none of them. The call made after jₖ records the set.

Nothing else is listed, and nothing twice. The constraint stops every path at the step that would cross the budget, so each recorded set fits. Positions only increase along a path, so each set has exactly one path from the root, and is recorded once. Skipping a branch loses nothing, for the reason above: every set below a skipped choice contains a set that is already over budget.

A dry run

The trace prints every call with its start and total, indented by depth, and every choice the constraint skips:

"""A dry run of topping_sets on the four-topping menu with a budget of 120: every call, every choice skipped."""
MENU = ["olives", "paneer", "corn", "onion"]
PRICES = [40, 70, 30, 50]
BUDGET = 120

chosen = []  # the state
calls = skips = 0


def backtrack(start, total, depth):
    global calls, skips
    calls += 1
    names = " + ".join(MENU[j] for j in chosen) or "plain"
    print(f"{'  ' * depth}backtrack({start}, {total})  records {names}")
    for j in range(start, len(PRICES)):
        if total + PRICES[j] > BUDGET:
            skips += 1
            print(f"{'  ' * (depth + 1)}skip {MENU[j]}: {total} + {PRICES[j]} = {total + PRICES[j]} > {BUDGET}")
            continue
        chosen.append(j)
        backtrack(j + 1, total + PRICES[j], depth + 1)
        chosen.pop()


backtrack(0, 0, 0)
print(f"{calls} calls, {skips} choices skipped; the state after the search: {chosen}")

backtrack(0, 0)  records plain
  backtrack(1, 40)  records olives
    backtrack(2, 110)  records olives + paneer
      skip corn: 110 + 30 = 140 > 120
      skip onion: 110 + 50 = 160 > 120
    backtrack(3, 70)  records olives + corn
      backtrack(4, 120)  records olives + corn + onion
    backtrack(4, 90)  records olives + onion
  backtrack(2, 70)  records paneer
    backtrack(3, 100)  records paneer + corn
      skip onion: 100 + 50 = 150 > 120
    backtrack(4, 120)  records paneer + onion
  backtrack(3, 30)  records corn
    backtrack(4, 80)  records corn + onion
  backtrack(4, 50)  records onion
12 calls, 3 choices skipped; the state after the search: []

Read it beside the tree. Each backtrack line is a solid box and each skip line a dashed one. At olives and paneer, 110, both remaining toppings break the budget, so that call records its set and returns. The set of all four toppings appears nowhere, not even as a skip: it would extend olives, paneer and corn, a branch the search never enters. The last line shows the contract at work: after 12 calls and 3 skips, chosen is empty again.

The code in five languages

The Python and JavaScript tabs have a Run button that works in this page. The Java, C++ and Go files are built and run in a terminal session, recorded below them.

"""Every set of toppings within a budget, listed by backtracking: choose, explore, unchoose."""

MENU = ["olives", "paneer", "corn", "onion"]
PRICES = [40, 70, 30, 50]


def topping_sets(prices, budget):
    """Every set of toppings whose prices add up to at most budget, as positions in menu order."""
    found = []
    chosen = []  # the state: the positions chosen so far, in menu order

    def backtrack(start, total):
        found.append(chosen.copy())  # goal: every state is within budget, so record a copy of it
        for j in range(start, len(prices)):  # choices: the toppings after the last one chosen
            if total + prices[j] > budget:  # constraint: never go over budget
                continue
            chosen.append(j)  # choose
            backtrack(j + 1, total + prices[j])  # explore
            chosen.pop()  # unchoose

    backtrack(0, 0)
    return found


def show(menu, prices, budget):
    sets = topping_sets(prices, budget)
    print(f"budget {budget}: {len(sets)} {'set' if len(sets) == 1 else 'sets'}")
    for s in sets:
        total = sum(prices[j] for j in s)
        print(f"{total:6}  {' + '.join(menu[j] for j in s) or 'plain'}")


if __name__ == "__main__":
    show(MENU, PRICES, 120)
    show(MENU, PRICES, 0)
    show(["paneer", "tofu"], [60, 60], 100)
    big = [40 + (37 * i) % 81 for i in range(40)]  # 40 toppings, each priced from 40 to 120
    print(f"40 toppings, budget 300: {len(topping_sets(big, 300))} sets")

budget 120: 12 sets
     0  plain
    40  olives
   110  olives + paneer
    70  olives + corn
   120  olives + corn + onion
    90  olives + onion
    70  paneer
   100  paneer + corn
   120  paneer + onion
    30  corn
    80  corn + onion
    50  onion
budget 0: 1 set
     0  plain
budget 100: 3 sets
     0  plain
    60  paneer
    60  tofu
40 toppings, budget 300: 49493 sets

// Every set of toppings within a budget, listed by backtracking: choose, explore, unchoose.
const MENU = ['olives', 'paneer', 'corn', 'onion'];
const PRICES = [40, 70, 30, 50];

/** Every set of toppings whose prices add up to at most budget, as positions in menu order. */
function toppingSets(prices, budget) {
  const found = [];
  const chosen = []; // the state: the positions chosen so far, in menu order
  const backtrack = (start, total) => {
    found.push([...chosen]); // goal: every state is within budget, so record a copy of it
    for (let j = start; j < prices.length; j++) { // choices: the toppings after the last one chosen
      if (total + prices[j] > budget) continue; // constraint: never go over budget
      chosen.push(j); // choose
      backtrack(j + 1, total + prices[j]); // explore
      chosen.pop(); // unchoose
    }
  };
  backtrack(0, 0);
  return found;
}

function show(menu, prices, budget) {
  const sets = toppingSets(prices, budget);
  console.log(`budget ${budget}: ${sets.length} ${sets.length === 1 ? 'set' : 'sets'}`);
  for (const s of sets) {
    const total = s.reduce((sum, j) => sum + prices[j], 0);
    console.log(`${String(total).padStart(6)}  ${s.map((j) => menu[j]).join(' + ') || 'plain'}`);
  }
}

show(MENU, PRICES, 120);
show(MENU, PRICES, 0);
show(['paneer', 'tofu'], [60, 60], 100);
const big = Array.from({ length: 40 }, (_, i) => 40 + ((37 * i) % 81)); // 40 toppings, each priced from 40 to 120
console.log(`40 toppings, budget 300: ${toppingSets(big, 300).length} sets`);

budget 120: 12 sets
     0  plain
    40  olives
   110  olives + paneer
    70  olives + corn
   120  olives + corn + onion
    90  olives + onion
    70  paneer
   100  paneer + corn
   120  paneer + onion
    30  corn
    80  corn + onion
    50  onion
budget 0: 1 set
     0  plain
budget 100: 3 sets
     0  plain
    60  paneer
    60  tofu
40 toppings, budget 300: 49493 sets

import java.util.ArrayList;
import java.util.List;

/** Every set of toppings within a budget, listed by backtracking: choose, explore, unchoose. */
public class Toppings {
    static final String[] MENU = {"olives", "paneer", "corn", "onion"};
    static final int[] PRICES = {40, 70, 30, 50};

    /** Every set of toppings whose prices add up to at most budget, as positions in menu order. */
    static List<List<Integer>> toppingSets(int[] prices, int budget) {
        List<List<Integer>> found = new ArrayList<>();
        backtrack(prices, budget, 0, 0, new ArrayList<>(), found);
        return found;
    }

    static void backtrack(int[] prices, int budget, int start, int total, List<Integer> chosen, List<List<Integer>> found) {
        found.add(new ArrayList<>(chosen)); // goal: record a copy; found.add(chosen) would store the one shared list
        for (int j = start; j < prices.length; j++) { // choices: the toppings after the last one chosen
            if (total + prices[j] > budget) continue; // constraint: never go over budget
            chosen.add(j); // choose
            backtrack(prices, budget, j + 1, total + prices[j], chosen, found); // explore
            chosen.removeLast(); // unchoose (chosen.remove(j) would remove the element at index j)
        }
    }

    static void show(String[] menu, int[] prices, int budget) {
        List<List<Integer>> sets = toppingSets(prices, budget);
        System.out.println("budget " + budget + ": " + sets.size() + (sets.size() == 1 ? " set" : " sets"));
        for (List<Integer> s : sets) {
            int total = 0;
            List<String> names = new ArrayList<>();
            for (int j : s) {
                total += prices[j];
                names.add(menu[j]);
            }
            System.out.printf("%6d  %s%n", total, names.isEmpty() ? "plain" : String.join(" + ", names));
        }
    }

    public static void main(String[] args) {
        show(MENU, PRICES, 120);
        show(MENU, PRICES, 0);
        show(new String[] {"paneer", "tofu"}, new int[] {60, 60}, 100);
        int[] big = new int[40]; // 40 toppings, each priced from 40 to 120
        for (int i = 0; i < big.length; i++) big[i] = 40 + (37 * i) % 81;
        System.out.println("40 toppings, budget 300: " + toppingSets(big, 300).size() + " sets");
    }
}

// Every set of toppings within a budget, listed by backtracking: choose, explore, unchoose.
#include <print>
#include <string>
#include <vector>

// Every set of toppings whose prices add up to at most budget, as positions in menu order.
std::vector<std::vector<int>> topping_sets(const std::vector<int>& prices, int budget) {
    std::vector<std::vector<int>> found;
    std::vector<int> chosen;  // the state: the positions chosen so far, in menu order
    // A recursive lambda: C++23 lets it name itself through an explicit object parameter (this auto&& self).
    auto backtrack = [&](this auto&& self, int start, int total) -> void {
        found.push_back(chosen);  // goal: push_back stores a copy of the vector
        for (int j = start; j < static_cast<int>(prices.size()); ++j) {  // choices
            if (total + prices[j] > budget) continue;  // constraint: never go over budget
            chosen.push_back(j);                       // choose
            self(j + 1, total + prices[j]);            // explore
            chosen.pop_back();                         // unchoose
        }
    };
    backtrack(0, 0);
    return found;
}

void show(const std::vector<std::string>& menu, const std::vector<int>& prices, int budget) {
    auto sets = topping_sets(prices, budget);
    std::println("budget {}: {} {}", budget, sets.size(), sets.size() == 1 ? "set" : "sets");
    for (const auto& s : sets) {
        int total = 0;
        std::string names;
        for (int j : s) {
            total += prices[j];
            names += (names.empty() ? "" : " + ") + menu[j];
        }
        std::println("{:6}  {}", total, names.empty() ? "plain" : names);
    }
}

int main() {
    const std::vector<std::string> menu = {"olives", "paneer", "corn", "onion"};
    const std::vector<int> prices = {40, 70, 30, 50};
    show(menu, prices, 120);
    show(menu, prices, 0);
    show({"paneer", "tofu"}, {60, 60}, 100);
    std::vector<int> big(40);  // 40 toppings, each priced from 40 to 120
    for (int i = 0; i < 40; ++i) big[i] = 40 + (37 * i) % 81;
    std::println("40 toppings, budget 300: {} sets", topping_sets(big, 300).size());
}

// Every set of toppings within a budget, listed by backtracking: choose, explore, unchoose.
package main

import (
	"fmt"
	"slices"
	"strings"
)

// toppingSets lists every set of toppings whose prices add up to at most budget, as positions in menu order.
func toppingSets(prices []int, budget int) [][]int {
	var found [][]int
	var chosen []int // the state: the positions chosen so far, in menu order
	var backtrack func(start, total int)
	backtrack = func(start, total int) {
		found = append(found, slices.Clone(chosen)) // goal: record a copy; chosen itself shares its array
		for j := start; j < len(prices); j++ {      // choices: the toppings after the last one chosen
			if total+prices[j] > budget { // constraint: never go over budget
				continue
			}
			chosen = append(chosen, j)      // choose
			backtrack(j+1, total+prices[j]) // explore
			chosen = chosen[:len(chosen)-1] // unchoose
		}
	}
	backtrack(0, 0)
	return found
}

func show(menu []string, prices []int, budget int) {
	sets := toppingSets(prices, budget)
	word := "sets"
	if len(sets) == 1 {
		word = "set"
	}
	fmt.Printf("budget %d: %d %s\n", budget, len(sets), word)
	for _, s := range sets {
		total, names := 0, []string{}
		for _, j := range s {
			total += prices[j]
			names = append(names, menu[j])
		}
		label := strings.Join(names, " + ")
		if label == "" {
			label = "plain"
		}
		fmt.Printf("%6d  %s\n", total, label)
	}
}

func main() {
	menu := []string{"olives", "paneer", "corn", "onion"}
	prices := []int{40, 70, 30, 50}
	show(menu, prices, 120)
	show(menu, prices, 0)
	show([]string{"paneer", "tofu"}, []int{60, 60}, 100)
	big := make([]int, 40) // 40 toppings, each priced from 40 to 120
	for i := range big {
		big[i] = 40 + (37*i)%81
	}
	fmt.Printf("40 toppings, budget 300: %d sets\n", len(toppingSets(big, 300)))
}

The session also runs one plausible bug, a Go version that records the slice chosen itself:

// A plausible bug in Go: record the slice chosen itself instead of a copy of it.
package main

import "fmt"

func toppingSets(prices []int, budget int) [][]int {
	var found [][]int
	var chosen []int
	var backtrack func(start, total int)
	backtrack = func(start, total int) {
		found = append(found, chosen) // the bug: this slice shares chosen's underlying array
		for j := start; j < len(prices); j++ {
			if total+prices[j] > budget {
				continue
			}
			chosen = append(chosen, j)
			backtrack(j+1, total+prices[j])
			chosen = chosen[:len(chosen)-1]
		}
	}
	backtrack(0, 0)
	return found
}

func main() {
	fmt.Println(toppingSets([]int{40, 70, 30, 50}, 120))
}

from session import run, versions

# Toppings.java runs as a single source file, toppings.cpp is built with the sanitizers on, go run builds the Go files.
versions("java -version", "clang++ --version", "go version")
run("""
java Toppings.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined toppings.cpp -o toppings && ./toppings
go run toppings.go
go run shared_slice.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Toppings.java
budget 120: 12 sets
     0  plain
    40  olives
   110  olives + paneer
    70  olives + corn
   120  olives + corn + onion
    90  olives + onion
    70  paneer
   100  paneer + corn
   120  paneer + onion
    30  corn
    80  corn + onion
    50  onion
budget 0: 1 set
     0  plain
budget 100: 3 sets
     0  plain
    60  paneer
    60  tofu
40 toppings, budget 300: 49493 sets
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined toppings.cpp -o toppings && ./toppings
budget 120: 12 sets
     0  plain
    40  olives
   110  olives + paneer
    70  olives + corn
   120  olives + corn + onion
    90  olives + onion
    70  paneer
   100  paneer + corn
   120  paneer + onion
    30  corn
    80  corn + onion
    50  onion
budget 0: 1 set
     0  plain
budget 100: 3 sets
     0  plain
    60  paneer
    60  tofu
40 toppings, budget 300: 49493 sets
$ go run toppings.go
budget 120: 12 sets
     0  plain
    40  olives
   110  olives + paneer
    70  olives + corn
   120  olives + corn + onion
    90  olives + onion
    70  paneer
   100  paneer + corn
   120  paneer + onion
    30  corn
    80  corn + onion
    50  onion
budget 0: 1 set
     0  plain
budget 100: 3 sets
     0  plain
    60  paneer
    60  tofu
40 toppings, budget 300: 49493 sets
$ go run shared_slice.go
[[] [0] [0 2] [0 2] [3 3 3] [3 3] [3] [3 3] [3 3] [3] [3 3] [3]]

All five versions print the same 12 sets, the same two edge cases and 49,493 sets for the 40-topping menu. Where they differ is the copy made when a set is recorded, the line where backtracking code most often goes wrong:

• Python: chosen.copy(), which the tutorial describes as a shallow copy, like chosen[:].
• JavaScript: [...chosen], a new array built with spread syntax.
• Java: new ArrayList<>(chosen). The undo is chosen.removeLast(), which List has had since Java 21 (JEP 431, sequenced collections). Avoid chosen.remove(j): with an int argument it calls remove(int index) and removes the element at position j, not the value j.
• C++: found.push_back(chosen) already copies, because standard containers are values. The recursive lambda names itself through this auto&& self, the explicit object parameter that C++23 added. The build turns on AddressSanitizer and UndefinedBehaviorSanitizer, which report memory errors and undefined behaviour as the program runs; this run reported none.
• Go: slices.Clone(chosen). A slice shares storage with its underlying array, and the Go specification says that append reuses that array whenever it has room, so a slice recorded without a copy keeps changing after it was recorded. The last command of the session shows the result: twelve entries of the right lengths, holding the wrong toppings.

The cost

Each call records one set, so the search makes exactly S calls. A call copies its set, at most n positions, and examines at most n choices, which gives O(n · S). The extra space is the recursion, at most n + 1 calls deep, and chosen, at most n positions. That is why the limits bound S as well as n: with S at most 100,000 and n = 40, the search takes a few million steps at most. Here are the counts on the 40-topping menu, priced from 40 to 120 with a budget of 300:

"""The 40-topping menu: how much work the search does, in menu order and with the cheapest toppings first."""
PRICES = [40 + (37 * i) % 81 for i in range(40)]  # 40 toppings, each priced from 40 to 120
BUDGET = 300


def search(prices, budget, cheapest_first):
    """Lists the sets within budget and counts the calls and the price checks of the search."""
    order = sorted(range(len(prices)), key=lambda j: prices[j]) if cheapest_first else list(range(len(prices)))
    found, chosen = [], []
    calls = checks = 0

    def backtrack(start, total):
        nonlocal calls, checks
        calls += 1
        found.append(sorted(chosen))  # a copy, in menu order
        for i in range(start, len(order)):
            j = order[i]
            checks += 1
            if total + prices[j] > budget:
                if cheapest_first:
                    break  # every topping after this one costs at least as much
                continue
            chosen.append(j)
            backtrack(i + 1, total + prices[j])
            chosen.pop()

    backtrack(0, 0)
    return found, calls, checks


in_order, calls_a, checks_a = search(PRICES, BUDGET, cheapest_first=False)
cheap, calls_b, checks_b = search(PRICES, BUDGET, cheapest_first=True)
assert sorted(in_order) == sorted(cheap)
print(f"40 toppings priced {min(PRICES)} to {max(PRICES)}, budget {BUDGET}")
print(f"subsets the brute force tries: {2 ** len(PRICES):>17,}")
print(f"sets within the budget:        {len(in_order):>17,}")
print(f"largest set:                   {max(map(len, in_order)):>17} toppings")
print(f"{'':24}{'calls':>9}{'price checks':>15}")
print(f"{'menu order, skip':24}{calls_a:>9,}{checks_a:>15,}")
print(f"{'cheapest first, stop':24}{calls_b:>9,}{checks_b:>15,}")

40 toppings priced 40 to 120, budget 300
subsets the brute force tries: 1,099,511,627,776
sets within the budget:                   49,493
largest set:                                   6 toppings
                            calls   price checks
menu order, skip           49,493        415,299
cheapest first, stop       49,493         96,615

There are 49,493 sets, so 49,493 calls, against 1,099,511,627,776 subsets for the brute force. The search in menu order checks 415,299 prices, about 8 per call, because a call keeps looking at toppings after one has failed to fit. Sorting the toppings by price allows a stronger cut: once one topping does not fit, no dearer one can, so the loop stops instead of skipping. That version makes the same 49,493 calls but checks only 96,615 prices, about 2 per call, which makes its work proportional to the size of the answer; it records each set sorted back into menu order. The largest set has 6 toppings, so the recursion never goes deeper than 7 calls.

Check it against the brute force

"""2,000 random menus: the backtracking search against the brute force."""
import random

from brute_force import topping_sets_brute
from toppings import topping_sets

rng = random.Random(16)
sets_seen = 0
for trial in range(2000):
    n = rng.randint(0, 10)
    prices = [rng.choice([1, 5, 10, rng.randint(1, 60)]) for _ in range(n)]  # many repeated prices
    budget = rng.randint(0, 70)
    fast = topping_sets(prices, budget)
    assert sorted(fast) == sorted(topping_sets_brute(prices, budget)), (prices, budget)
    assert len({tuple(s) for s in fast}) == len(fast), "a set was listed twice"
    assert all(s == sorted(s) for s in fast), "a set is not in menu order"
    sets_seen += len(fast)
print(f"2,000 random menus of 0 to 10 toppings: both list the same {sets_seen:,} sets, none twice")

2,000 random menus of 0 to 10 toppings: both list the same 139,814 sets, none twice

The prices are drawn so that 1, 5 and 10 come up often, which gives many repeated prices and many totals that land exactly on the budget, where a > written as >= would show. The two functions list their sets in different orders, so the check sorts both lists before comparing them. It also checks that no set appears twice and that every set is in menu order.

Edge cases and common bugs

• A budget of 0 leaves only the plain pizza, and a topping dearer than the budget is skipped by every call and appears in no set.
• Equal prices belong to different toppings: a set is made of positions, not prices.
• > or >=: a set that costs exactly the budget fits. With >= in the constraint, olives, corn and onion at 120 would be lost, and so would paneer and onion.

The most damaging bugs are in the three moves. Forgetting to unchoose leaves each choice in the state while the next option is tried:

"""A plausible bug: choose and explore, but never unchoose."""
MENU = ["olives", "paneer", "corn", "onion"]
PRICES = [40, 70, 30, 50]


def topping_sets_no_undo(prices, budget):
    found = []
    chosen = []

    def backtrack(start, total):
        found.append(chosen.copy())
        for j in range(start, len(prices)):
            if total + prices[j] > budget:
                continue
            chosen.append(j)
            backtrack(j + 1, total + prices[j])
            # the bug: chosen.pop() is missing, so this choice stays in the state for the next one

    backtrack(0, 0)
    return found


sets = topping_sets_no_undo(PRICES, 120)
for s in sets:
    total = sum(PRICES[j] for j in s)
    print(f"{total:6}  {' + '.join(MENU[j] for j in s) or 'plain'}{'  over budget' if total > 120 else ''}")
print(len(sets), "entries,", sum(sum(PRICES[j] for j in s) > 120 for s in sets), "of them over budget")

     0  plain
    40  olives
   110  olives + paneer
   140  olives + paneer + corn  over budget
   190  olives + paneer + corn + onion  over budget
   240  olives + paneer + corn + onion + onion  over budget
   310  olives + paneer + corn + onion + onion + paneer  over budget
   340  olives + paneer + corn + onion + onion + paneer + corn  over budget
   390  olives + paneer + corn + onion + onion + paneer + corn + onion  over budget
   420  olives + paneer + corn + onion + onion + paneer + corn + onion + corn  over budget
   470  olives + paneer + corn + onion + onion + paneer + corn + onion + corn + onion  over budget
   520  olives + paneer + corn + onion + onion + paneer + corn + onion + corn + onion + onion  over budget
12 entries, 9 of them over budget

There are still 12 entries, so a test that compares only the number of answers passes. But 9 of the 12 are over budget, and the lists keep growing. The totals passed down are right and only the state is wrong, which is why the bug stays quiet until someone reads an answer. Recording the state itself instead of a copy goes wrong differently:

"""A plausible bug: record the state itself instead of a copy of it."""


def topping_sets_no_copy(prices, budget):
    found = []
    chosen = []

    def backtrack(start, total):
        found.append(chosen)  # the bug: every entry is the same list object
        for j in range(start, len(prices)):
            if total + prices[j] > budget:
                continue
            chosen.append(j)
            backtrack(j + 1, total + prices[j])
            chosen.pop()

    backtrack(0, 0)
    return found


print(topping_sets_no_copy([40, 70, 30, 50], 120))

[[], [], [], [], [], [], [], [], [], [], [], []]

Again 12 entries, and all of them are the same list object. It ends empty, because every choice was undone on the way back. Both bugs keep the shape of the search, so test what the answers contain, not only how many there are.

Variants

• Find one set instead of all: return as soon as the goal is reached, and pass the success back up so that every caller stops as well. The early return skips the unchoose lines on the way out, so the state still holds that set afterwards.
• Count the sets without listing them: drop the recording; the count is the number of calls. When the budget is small, dynamic programming over (position, total) counts the sets without visiting each one.
• Toppings that may be taken more than once: recurse with start = j instead of j + 1, so that the same topping can be chosen again for as long as the budget allows; a later lesson of this module builds combination sums this way.

Follow-up questions

The menu grows to 60 toppings. Does the method still work? Only while the number of sets within budget stays small, because the search makes one call per set. The 2⁶⁰ subsets no longer matter, but a generous budget can still allow billions of sets, and then no method lists them in time. If only the number of sets is wanted, count them with dynamic programming instead.

Can the search run without recursion? Yes. Keep an explicit stack of (start, total, chosen) entries, pop one, record its set and push one entry for each choice that fits. Each entry then needs a copy of its set, because without returning calls there is no moment to undo a choice. Recursion keeps the cheap undo, and its depth here is at most 41 calls, so Python’s recursion limit is no concern.

Undo or copy? Timed at n = 20

A search could also give every call its own copy of the state, such as chosen + [j] in Python, and never undo anything. That is shorter to write and cannot leave a stale choice behind, so it is worth measuring what it costs. This program runs the same search over all 2²⁰ subsets of 20 items both ways, for three sizes of state:

"""Copying the state at every call against changing it and undoing the change, on all 2**20 subsets of 20 items."""
import time

N = 20


def copy_flat(size):
    """Every call gets a new list of `size` items, with one item changed."""

    def build(start, state):
        for j in range(start, N):
            child = state.copy()  # size items written for this call
            child[j] = j
            build(j + 1, child)

    build(0, [0] * size)


def undo_flat(size):
    """One list of `size` items for the whole search: change one item, explore, put the old value back."""
    state = [0] * size

    def build(start):
        for j in range(start, N):
            old = state[j]
            state[j] = j  # choose
            build(j + 1)  # explore
            state[j] = old  # unchoose

    build(0)


def copy_board(_size):
    """Every call gets a new 9 x 9 board, copied row by row, with one cell changed."""

    def build(start, board):
        for j in range(start, N):
            child = [row.copy() for row in board]  # 10 new lists and 81 cells for this call
            child[j % 9][j // 9] = j
            build(j + 1, child)

    build(0, [[0] * 9 for _ in range(9)])


def undo_board(_size):
    """One 9 x 9 board for the whole search: change one cell, explore, put the old value back."""
    board = [[0] * 9 for _ in range(9)]

    def build(start):
        for j in range(start, N):
            old = board[j % 9][j // 9]
            board[j % 9][j // 9] = j  # choose
            build(j + 1)  # explore
            board[j % 9][j // 9] = old  # unchoose

    build(0)


def seconds(search, size):
    start = time.perf_counter()
    search(size)
    return time.perf_counter() - start


def best_of(copy, undo, size, rounds=3):
    """The fastest of a few runs of each, taken in turns: other programs on the computer slow single runs down."""
    times = [(seconds(copy, size), seconds(undo, size)) for _ in range(rounds)]
    return min(t for t, _ in times), min(t for _, t in times)


print(f"{2**N:,} calls in each search")
print(f"{'the state':<24}{'items copied':>14}{'copying':>10}{'undoing':>10}")
for label, size, copy, undo in [
    ("20 positions", 20, copy_flat, undo_flat),
    ("a 9 x 9 board", 81, copy_board, undo_board),
    ("1,000 items", 1000, copy_flat, undo_flat),
]:
    copied = (2**N - 1) * size  # every call but the first copies the whole state
    t_copy, t_undo = best_of(copy, undo, size)
    print(f"{label:<24}{copied:>14,}{t_copy:>8.2f} s{t_undo:>8.2f} s")

1,048,576 calls in each search
the state                 items copied   copying   undoing
20 positions                20,971,500    0.19 s    0.14 s
a 9 x 9 board               84,934,575    0.93 s    0.23 s
1,000 items              1,048,575,000    2.32 s    0.17 s

The counts do not depend on the computer. Copying writes the whole state for every call but the first: 20,971,500 items for a state of 20, and over a billion for a state of 1,000. Undoing writes two items per call, whatever the size of the state. The times show what that means in CPython. With 20 items the two are close, and on a busy computer either may come out ahead, because copying a short list is one quick step inside the interpreter and the function call around it costs more. The gap grows with the state: copying a 9 × 9 board row by row, as a Sudoku solver might, and copying a state of 1,000 items left copying far behind undoing in the recorded run.

The rule that follows: change the state and undo the change during the search, and copy only when you record an answer. The copy at the goal cannot be avoided, since every recorded answer must survive later changes, and it is part of the cost of writing the output anyway. Copying at every step is reasonable when the state is a couple of numbers, such as an immutable pair of counters, and a poor default when it is a board, a grid of visited marks or a long path.

How big is the search tree?

Before writing a backtracking solution, estimate how many calls it can make. Each call holds one state the search can reach, so count the states. Three shapes cover most problems:

• Every subset of n items, each in or out: one call per subset, 2ⁿ calls.
• Every ordering of n items: one call per partial ordering, n!/n! + n!/(n − 1)! + … + n!/0!, which is about e · n!, a little under three times the number of complete orderings.
• Every choice of k items out of n, made in increasing order: one call per set of at most k items, C(n, 0) + C(n, 1) + … + C(n, k).

This program counts the calls of each shape on small inputs, checks every count against its formula, and then uses the formulas for larger n:

"""How many calls a backtracking search makes before any pruning: counted on small inputs, then by formula."""
from math import comb, perm


def subset_calls(n):
    """Calls of the start-index search over every subset of n items (one call per subset)."""
    calls = 0

    def backtrack(start):
        nonlocal calls
        calls += 1
        for j in range(start, n):
            backtrack(j + 1)

    backtrack(0)
    return calls


def ordering_calls(n):
    """Calls of a search over every ordering of n items (one call per partial ordering)."""
    calls = 0
    used = [False] * n

    def backtrack(placed):
        nonlocal calls
        calls += 1
        for j in range(n):
            if not used[j]:
                used[j] = True
                backtrack(placed + 1)
                used[j] = False

    backtrack(0)
    return calls


def choose_calls(n, k):
    """Calls of a search that chooses k of n items in increasing order (one call per set of at most k items)."""
    calls = 0

    def backtrack(start, size):
        nonlocal calls
        calls += 1
        if size == k:
            return
        for j in range(start, n):
            backtrack(j + 1, size + 1)

    backtrack(0, 0)
    return calls


# The formulas: one call for every state the search can reach.
FORMULAS = {
    "every subset": lambda n: 2**n,
    "every ordering": lambda n: sum(perm(n, i) for i in range(n + 1)),  # n!/n! + n!/(n-1)! + ... + n!/0!
    "choose 3 of n": lambda n: sum(comb(n, i) for i in range(4)),
}
COUNTERS = {"every subset": subset_calls, "every ordering": ordering_calls, "choose 3 of n": lambda n: choose_calls(n, 3)}

print(f"{'counted':<16}{'n':>3}{'calls':>10}{'formula':>10}")
for shape, n in [("every subset", 10), ("every subset", 16), ("every ordering", 5), ("every ordering", 8), ("choose 3 of n", 10), ("choose 3 of n", 20)]:
    counted, expected = COUNTERS[shape](n), FORMULAS[shape](n)
    assert counted == expected
    print(f"{shape:<16}{n:>3}{counted:>10,}{expected:>10,}")
print()
print(f"{'by formula':<16}{'n = 10':>14}{'n = 15':>20}{'n = 20':>28}")
for shape, formula in FORMULAS.items():
    print(f"{shape:<16}" + "".join(f"{formula(n):>{w},}" for n, w in [(10, 14), (15, 20), (20, 28)]))

counted           n     calls   formula
every subset     10     1,024     1,024
every subset     16    65,536    65,536
every ordering    5       326       326
every ordering    8   109,601   109,601
choose 3 of n    10       176       176
choose 3 of n    20     1,351     1,351

by formula              n = 10              n = 15                      n = 20
every subset             1,024              32,768                   1,048,576
every ordering       9,864,101   3,554,627,472,076   6,613,313,319,248,080,001
choose 3 of n              176                 576                       1,351

Read the second table as a budget. About a million calls, every subset of 20 items, takes a fraction of a second even in Python, as the timed run above shows. About ten million, every ordering of 10 items, takes several seconds. Every ordering of 15 items is over three trillion calls, which no language finishes in an interview’s time. Pruning can make the real tree far smaller, but the count without pruning is the safe upper bound, and the right first estimate when nothing is known about the data. Then compare it with the rough budgets of the lesson on constraints.

The output sets a lower bound too. All the subsets of n items hold n · 2ⁿ⁻¹ items between them, because each item is in half of the subsets: 10,485,760 items when n = 20. No program writes them in fewer steps, so listing every subset takes Ω(n · 2ⁿ) time, and a search that does O(n) work per call is as fast as listing can be. When that bound is too large, the fix is a different question, such as a count or a best answer, solved by another method, rather than a faster search.

Exercise

wardrobe = [["white tee", "striped shirt"], ["jeans", "chinos"]]
outfits(wardrobe, [("striped shirt", "chinos")])
# [["white tee", "jeans"], ["white tee", "chinos"], ["striped shirt", "jeans"]]

def outfits(wardrobe, clashes):
    """Every outfit of one item of each kind, with no clashing pair, in the order the kinds are listed."""
    # Replace this line with your code.
    return []

import random
from itertools import combinations, product

from outfits import outfits

TOPS = ["white tee", "striped shirt"]
BOTTOMS = ["jeans", "chinos"]


def trusted(wardrobe, clashes):
    """The answer the tests trust: every combination, kept when no two of its items clash."""
    bad = {frozenset(pair) for pair in clashes}
    return [list(o) for o in product(*wardrobe) if not any(frozenset(p) in bad for p in combinations(o, 2))]


def test_prompt_example():
    """the example of the prompt: the striped shirt clashes with the chinos"""
    assert outfits([TOPS, BOTTOMS], [("striped shirt", "chinos")]) == [
        ["white tee", "jeans"],
        ["white tee", "chinos"],
        ["striped shirt", "jeans"],
    ]


def test_no_clashes():
    """with no clashes every combination is an outfit, in the order of the kinds' items"""
    shoes = ["sneakers", "sandals", "boots"]
    assert outfits([TOPS, shoes], []) == [
        ["white tee", "sneakers"],
        ["white tee", "sandals"],
        ["white tee", "boots"],
        ["striped shirt", "sneakers"],
        ["striped shirt", "sandals"],
        ["striped shirt", "boots"],
    ]


def test_pairs_in_either_order():
    """a clash counts whichever item of the pair comes first"""
    assert outfits([TOPS, BOTTOMS], [("chinos", "striped shirt")]) == [
        ["white tee", "jeans"],
        ["white tee", "chinos"],
        ["striped shirt", "jeans"],
    ]


def test_clash_between_first_and_last_kinds():
    """a top can clash with shoes, two kinds apart"""
    wardrobe = [TOPS, BOTTOMS, ["sneakers", "boots"]]
    assert outfits(wardrobe, [("white tee", "boots")]) == [
        ["white tee", "jeans", "sneakers"],
        ["white tee", "chinos", "sneakers"],
        ["striped shirt", "jeans", "sneakers"],
        ["striped shirt", "jeans", "boots"],
        ["striped shirt", "chinos", "sneakers"],
        ["striped shirt", "chinos", "boots"],
    ]


def test_a_kind_with_no_items():
    """a kind with no items leaves no outfit"""
    assert outfits([TOPS, []], []) == []


def test_no_kinds():
    """a wardrobe with no kinds has one outfit, the empty one"""
    assert outfits([], []) == [[]]


def test_one_kind():
    """with one kind, no outfit holds two items, so no clash can apply"""
    assert outfits([["red cap", "blue cap", "no cap"]], [("red cap", "blue cap")]) == [["red cap"], ["blue cap"], ["no cap"]]


def test_everything_clashes():
    """every top clashes with every bottom: no outfit"""
    clashes = [(t, b) for t in TOPS for b in BOTTOMS]
    assert outfits([TOPS, BOTTOMS], clashes) == []


def test_outfits_are_separate_lists():
    """changing one returned outfit changes no other, and the wardrobe is left as it was"""
    wardrobe = [TOPS.copy(), BOTTOMS.copy()]
    found = outfits(wardrobe, [])
    found[0].append("scarf")
    assert found[1:] == [["white tee", "chinos"], ["striped shirt", "jeans"], ["striped shirt", "chinos"]]
    assert wardrobe == [TOPS, BOTTOMS]


def test_sixteen_kinds():
    """16 kinds of 3 items, 43,046,721 combinations: an item clashes with the other letters of the next kind"""
    wardrobe = [[f"{letter}{kind}" for letter in "abc"] for kind in range(16)]
    clashes = [(f"{x}{kind}", f"{y}{kind + 1}") for kind in range(15) for x in "abc" for y in "abc" if x != y]
    assert outfits(wardrobe, clashes) == [[f"{letter}{kind}" for kind in range(16)] for letter in "abc"]


def test_random_wardrobes():
    """300 random wardrobes, checked against trying every combination"""
    rng = random.Random(16)
    for _ in range(300):
        wardrobe = [[f"item{kind}.{i}" for i in range(rng.randint(0, 3))] for kind in range(rng.randint(0, 4))]
        items = [item for kind in wardrobe for item in kind]
        pairs = list(combinations(items, 2))
        clashes = rng.sample(pairs, rng.randint(0, len(pairs)))
        clashes = [tuple(reversed(p)) if rng.random() < 0.5 else p for p in clashes]
        assert outfits(wardrobe, clashes) == trusted(wardrobe, clashes), f"wardrobe {wardrobe}, clashes {clashes}"

/** Every outfit of one item of each kind, with no clashing pair, in the order the kinds are listed. */
export function outfits(wardrobe, clashes) {
  // Replace this line with your code.
  return [];
}

import { test, assert } from 'mysmartcopilot:test';
import { outfits } from './outfits.mjs';

const TOPS = ['white tee', 'striped shirt'];
const BOTTOMS = ['jeans', 'chinos'];

let seed = 16;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
const randInt = (lo, hi) => lo + Math.floor(random() * (hi - lo + 1));

/** The answer the tests trust: every combination, kept when no two of its items clash. */
function trusted(wardrobe, clashes) {
  const bad = new Set(clashes.map(([a, b]) => [a, b].sort().join('\u0000')));
  let combos = [[]];
  for (const kind of wardrobe) combos = combos.flatMap((c) => kind.map((item) => [...c, item]));
  return combos.filter((o) => o.every((x, i) => o.every((y, j) => j <= i || !bad.has([x, y].sort().join('\u0000')))));
}

test('the example of the prompt: the striped shirt clashes with the chinos', () => {
  assert.deepEqual(outfits([TOPS, BOTTOMS], [['striped shirt', 'chinos']]), [
    ['white tee', 'jeans'],
    ['white tee', 'chinos'],
    ['striped shirt', 'jeans'],
  ]);
});

test("with no clashes every combination is an outfit, in the order of the kinds' items", () => {
  assert.deepEqual(outfits([TOPS, ['sneakers', 'sandals', 'boots']], []), [
    ['white tee', 'sneakers'],
    ['white tee', 'sandals'],
    ['white tee', 'boots'],
    ['striped shirt', 'sneakers'],
    ['striped shirt', 'sandals'],
    ['striped shirt', 'boots'],
  ]);
});

test('a clash counts whichever item of the pair comes first', () => {
  assert.deepEqual(outfits([TOPS, BOTTOMS], [['chinos', 'striped shirt']]), [
    ['white tee', 'jeans'],
    ['white tee', 'chinos'],
    ['striped shirt', 'jeans'],
  ]);
});

test('a top can clash with shoes, two kinds apart', () => {
  assert.deepEqual(outfits([TOPS, BOTTOMS, ['sneakers', 'boots']], [['white tee', 'boots']]), [
    ['white tee', 'jeans', 'sneakers'],
    ['white tee', 'chinos', 'sneakers'],
    ['striped shirt', 'jeans', 'sneakers'],
    ['striped shirt', 'jeans', 'boots'],
    ['striped shirt', 'chinos', 'sneakers'],
    ['striped shirt', 'chinos', 'boots'],
  ]);
});

test('a kind with no items leaves no outfit, and a wardrobe with no kinds has one, the empty one', () => {
  assert.deepEqual(outfits([TOPS, []], []), []);
  assert.deepEqual(outfits([], []), [[]]);
});

test('with one kind, no clash can apply; when every top clashes with every bottom, no outfit is left', () => {
  assert.deepEqual(outfits([['red cap', 'blue cap', 'no cap']], [['red cap', 'blue cap']]), [['red cap'], ['blue cap'], ['no cap']]);
  assert.deepEqual(outfits([TOPS, BOTTOMS], TOPS.flatMap((t) => BOTTOMS.map((b) => [t, b]))), []);
});

test('changing one returned outfit changes no other, and the wardrobe is left as it was', () => {
  const wardrobe = [[...TOPS], [...BOTTOMS]];
  const found = outfits(wardrobe, []);
  found[0].push('scarf');
  assert.deepEqual(found.slice(1), [['white tee', 'chinos'], ['striped shirt', 'jeans'], ['striped shirt', 'chinos']]);
  assert.deepEqual(wardrobe, [TOPS, BOTTOMS]);
});

test('16 kinds of 3 items, 43,046,721 combinations: an item clashes with the other letters of the next kind', () => {
  const kinds = Array.from({ length: 16 }, (_, k) => k);
  const wardrobe = kinds.map((k) => ['a', 'b', 'c'].map((letter) => `${letter}${k}`));
  const clashes = [];
  for (const k of kinds.slice(0, 15)) for (const x of 'abc') for (const y of 'abc') if (x !== y) clashes.push([`${x}${k}`, `${y}${k + 1}`]);
  assert.deepEqual(outfits(wardrobe, clashes), ['a', 'b', 'c'].map((letter) => kinds.map((k) => `${letter}${k}`)));
});

test('300 random wardrobes, checked against trying every combination', () => {
  for (let trial = 0; trial < 300; trial++) {
    const wardrobe = Array.from({ length: randInt(0, 4) }, (_, k) => Array.from({ length: randInt(0, 3) }, (_, i) => `item${k}.${i}`));
    const items = wardrobe.flat();
    const clashes = [];
    for (let i = 0; i < items.length; i++) {
      for (let j = i + 1; j < items.length; j++) {
        if (random() < 0.3) clashes.push(random() < 0.5 ? [items[i], items[j]] : [items[j], items[i]]);
      }
    }
    assert.deepEqual(outfits(wardrobe, clashes), trusted(wardrobe, clashes), JSON.stringify([wardrobe, clashes]));
  }
});

Interview questions

Fresher · What is backtracking, and how is it different from a brute force?

Backtracking builds a candidate one decision at a time and checks the rules after every decision. When a partial candidate already breaks a rule, it abandons that branch, undoes the last decision and tries the next option, so the candidates that would have grown from the failed part are never built. A brute force builds every complete candidate first and checks each one at the end. Both walk the same tree of decisions, and when nothing fails early they do the same work; the difference is the pruning. In the toppings problem a set over budget stays over budget whatever is added, so the search visits only the sets that fit: 49,493 calls for 40 toppings, where the brute force would build all 2⁴⁰ subsets. When every candidate must be listed anyway, the size of the output limits both.

Fresher · Which four things do you decide before writing a backtracking function?

The state, the choices, the goal and the constraints. The state is what has been decided so far, kept in one place that every call shares and changes, such as a list of chosen items. The choices are what may come next from the current state, for example only the items after the last one chosen, so that no set is built in two orders. The goal says when the state is a complete answer; the function then records a copy, because the state will change again. The constraints say when a choice cannot lead to any answer, so the search skips it and everything below it. With the four named, the code follows: a loop over the choices that skips what the constraints rule out, and for every other choice, choose, explore with a recursive call, unchoose.

Key takeaways

• Backtracking is a depth-first search of a tree of partial answers: choose, explore, unchoose.
• Name the state, the choices, the goal and the constraints before writing code; the function is a loop over the choices with the three moves inside it.
• The contract of a call is that it leaves the state as it found it, which lets every option start from the same state.
• Prune as soon as a partial answer breaks a rule. On the 40-topping menu that turned 2⁴⁰ subsets into 49,493 calls, and sorting the prices cut the price checks from 415,299 to 96,615.
• Change the state and undo the change; copy only when you record an answer, and in Go clone the slice.
• Size the tree before running it: 2ⁿ calls for subsets, about e · n! for orderings, and never fewer steps than the output holds.