Choose, Explore, Unchoose

Most backtracking code is a disciplined repetition of three operations. Choose applies one candidate move to the current state. Explore recurses from the modified state. Unchoose restores the state so the next move can be tried from the same parent.

This rhythm is more than a coding convention. It is the correctness contract that makes a DFS tree walk possible with shared mutable objects instead of cloning the entire state at every edge.

Recursive calls share references to objects like path, used[], board, and running counters. If one branch appends a value or marks a cell and never restores it, the sibling branch starts from a polluted state. The output may contain extra values, miss solutions, or reject valid paths.

Undoing makes each recursive frame behave as if it owns a clean snapshot of the parent state. You get the memory efficiency of mutation with the reasoning clarity of separate branches.

A path list is usually undone by removing the last element. A used[] array is undone by resetting the chosen index to false. A board cell is undone by putting back the original marker or clearing the placement. A running sum is often passed by value, so it may not need an explicit undo.

The rule is simple: if the choice mutates shared state, the exact inverse mutation belongs after the recursive call. If a value is passed into the next frame as a new primitive value, Java restores it automatically when the frame returns.

Backtracking bugs are often asymmetry bugs. Look at every line that changes state before recursion and make sure a matching line restores it after recursion. The restore operation should usually be close to the recursive call so the pairing is visually obvious.

When multiple fields change together, undo them in a consistent reverse order. That habit prevents subtle mistakes in board problems where a row placement may update columns, diagonals, and the visible board at the same time.