Keep backtracking branches independent

At each recursive call, define what the partial state represents and which choices remain. Apply a choice before exploring it, then undo that change after the call returns. Starting each branch from the same state prevents one path from leaking changes into another.