Backtracking

Backtracking explores a decision tree while keeping one mutable partial solution. Begin by defining what a recursion level means, for example the first row not yet assigned for N-Queens or the next position in a subset. At each call, check the completion condition, then try every candidate that is currently valid. Apply the candidate, recurse, and undo exactly the mutation before trying the next candidate. Pruning should be based on a necessary condition: a partial placement that already conflicts cannot become valid later. Avoid storing a reference to the mutable path when collecting answers; append a copy at the base case. Test an empty candidate set, a solution with one decision, no solution, and duplicate candidates. Runtime is generally exponential in the number of decisions, such as O(b to the d) for branching factor b and depth d, although output size may itself dominate; recursion state is O(d) excluding results.