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 explores partial assignments and undoes a choice before trying the next. A used-value set enforces uniqueness as soon as a candidate is considered, rather than discovering duplicates after a complete assignment. Sort and deduplicate each position's choices to make the first successful complete path lexicographically smallest.

Undoing a choice that blocks the next slot

Choose A for the first slot and mark it used. The second slot now has no legal name, so remove A from both the working path and used set before trying B. The second slot can then take A. In input-slot order, trying sorted unique names means the first complete assignment is also the lexicographically smallest one.

std::set<Text> used;
auto [it,inserted]=used.insert(U"A");
if(inserted) { /* explore */ used.erase(it); }

Pruning does not remove the worst case

Do not confuse lexicographically sorting the final chosen values with choosing the smallest valid vector in input-position order. For choices {A,B} then {A}, greedily choosing A fails, so the search must backtrack to B. Empty input has one complete assignment: the empty vector. An empty inner choice list has none. These differ naturally through recursion's base case. Pruning avoids invalid prefixes but worst-case work remains exponential. Own sorted copies so neither nested input vector is changed.

Early rejection avoids exploring all descendants of an invalid prefix, but worst-case search is still exponential. The path, used-name set, and recursion stack grow with the number of slots, in addition to prepared choice lists. Reordering slots can improve search but requires care to preserve the requested canonical result.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged. Text ordering follows Unicode code points (Text) or the documented UTF-8 identifier order (std::string).

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