Backtracking and pruning

An event needs one volunteer in each slot, and each volunteer can cover at most one slot. The first slot allows A or B; the second allows only A. Choosing the first available name greedily leaves the second slot empty, even though B, A works.

Backtracking keeps an early choice provisional. When it blocks completion, undo it and try the next option. The app also wants a deterministic result, so the order in which alternatives are tried matters.

Assigning volunteers without double booking

Backtracking constructs a partial assignment, explores what can follow it, then undoes the choice before trying another branch. The problem chooses one string per position while forbidding repeated strings. Enumerating complete combinations first is a simple baseline, but it wastes work on prefixes already containing a conflict.

The required result is the smallest valid vector in original position order. Sorting the chosen output values would destroy that positional meaning.

Undoing a choice that blocks the next slot

Sort and deduplicate each position's available choices, then try them in that order. A used-value Set rejects a repeated string immediately. On failure, remove that choice from both the partial vector and the used set before trying the next candidate. The first complete path is lexicographically smallest because earlier choices have been exhausted in sorted order.

For options [["A", "B"], ["A"]], choosing A at the first position leaves no valid second choice, so the search must undo A and try B. A greedy choice without rollback would incorrectly report impossibility. Empty input already is a complete empty assignment; an empty inner list permits no complete assignment.

Use the supplied compareText helper for Unicode code-point ordering. Default sorting and localeCompare do not supply the same total order. Build sorted unique copies of each option list so pruning and ordering do not mutate caller-owned nested arrays.

import { compareText } from "./exercise.mjs";
const options = ["😀", "", "😀"];
const ordered = [...new Set(options)].sort(compareText);
console.log(ordered); // ["", "😀"]: U+E000 precedes U+1F600
console.log(options.length); // 3: source choices remain unchanged

Pruning does not remove the worst case

Early rejection prunes impossible prefixes, but worst-case search remains exponential in the number of positions and choices. Sorting each position has its own preprocessing cost, and recursion/used-set state grows with assignment depth. This model suits uniqueness-constrained small searches; large matching problems may admit polynomial matching algorithms when only existence is required rather than this particular search exercise.

A specialized matching algorithm is worth considering when the volunteer roster outgrows a manageable decision tree.