{title}

{title} explains restoring mutable state before trying a sibling branch. The key idea is to mutate a partial state, recursively explore from it, and restore it before the next option.

Topic

Backtracking Fundamentals

Pattern

Choose Explore Undo

Time

Depends on branching

Space

O(depth)

Call tree simulation

initial state

depth 0

choice

state

choice

explore

choice

undo

Code Tracker

:::

1void backtrack(state) {

2 if (isAnswer(state)) { save(state); return; }

3 for (choice : choices) {

4 if (!allowed(choice, state)) continue;

5 apply(choice, state);

6 backtrack(state);

7 undo(choice, state);

8 }

Loading Lab...

Undo Backtrack Step

Undo Backtrack Step

{title}

{title}