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 grows a partial assignment, rejecting it as soon as it violates uniqueness. After exploring a choice, undo its effect before a sibling branch. A shared used set represents only the current path.

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.

used := map[string]bool{"worker-a": true}
delete(used, "worker-a") // rollback a path-local choice

Pruning does not remove the worst case

Input-position order determines the output tuple. Reordering variables may improve search but changes how the lexicographically first answer is found. Sorted unique alternatives and depth-first traversal provide a canonical result. Returning the working slice directly can let later rollback corrupt a saved answer; copy at the ownership boundary. Assignment and configuration searches commonly use this pattern.

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.

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