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

Assign one unique label per position while producing the lexicographically smallest complete assignment. A locally smallest choice may need to be undone when a later position has no alternative.

Generating complete products and checking uniqueness at the end wastes work on already-impossible prefixes. Early rejection and rollback prune the search, but sorted options alone do not prove that the first local choice can remain committed.

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.

Backtracking owns one choice per input position and a set of choices already used. Remove the tentative choice on every failed branch. Sorted unique options and the first complete success produce a canonical assignment. Pruning rejects impossible partial states but worst-case work remains exponential.

The first position must sometimes give up its preferred label so the second can complete:

import java.util.*;

class Example {
    public static void main(String[] args) {
        List<String> first = List.of("A", "B");
        List<String> second = List.of("A");
        Set<String> used = new HashSet<>(List.of("A"));
        assert second.stream().noneMatch(label -> !used.contains(label));
        used.remove("A"); // undo the tentative choice before another branch
        assert !used.contains("A");
    }
}

Only state introduced by the failing branch should be removed. The search must restore both the chosen-prefix list and the used-label set before trying another option. A full assignment is a stronger success condition than a nonempty partial prefix.

Pruning does not remove the worst case

Constraint search is useful for small matching/placement problems where direct greedy decisions can fail. Pruning improves practical work but does not remove worst-case exponential behavior; larger special cases may need a matching algorithm.

Choose one string per inner list with no string reused; return the lexicographically smallest full assignment in input-position order, or null. Empty outer input returns an empty list; an empty option list makes completion impossible. Duplicate options count once. Java ordering is String.compareTo (UTF-16 lexical order).

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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