The backtracking template: choose, explore, undo

Backtracking Junior Python 3.13+ Reviewed By Best Latest Apps

Order the steps

Order the parts of a backtracking function.

  • Check if the branch can be pruned
  • Apply the choice, recurse, then undo it
  • Loop over the choices for the next step
  • Check if the path is complete and record a copy

Choose an answer, then open Show answer below to check it.

Show answer

Answer: D A C B

  1. Check if the path is complete and record a copy This is the base case.
  2. Check if the branch can be pruned Stop early when no answer can come from here.
  3. Loop over the choices for the next step Each choice is one child in the decision tree.
  4. Apply the choice, recurse, then undo it Undoing restores the state for the next choice.

30-second answer

Backtracking builds a solution one choice at a time. At each step it makes a choice, recurses to make the rest, then undoes the choice so the next option starts from a clean state. Record an answer when the path is complete; stop a branch the moment it cannot lead to one. The cost is the size of the decision tree, often exponential, so pruning matters.

Practise saying it · 45 s. No recording, just a timer

Explain the backtracking template.

Say your answer out loud, then check which of these points you covered:

  • Choose
  • Explore
  • Undo

Deep dive

Three questions shape every version: what is a choice, when is a path complete, and when can a branch be cut early.

Shared mutable state (a path list, used flags) plus undo is faster than copying state at each call.

Return early with True when you need just one solution.

Common mistakes

  • Forgetting to undo, so later branches see stale state.
  • Recording the live path instead of a copy.

Senior take & follow-ups

Name the three questions out loud before coding a backtracking answer.

Follow-up questions

Think of your answer first, then open the hint.

  1. How is backtracking different from DFS?

    Show hint

    It is DFS over the tree of partial solutions, with state undone on the way back.

  2. When should you switch to DP?

    Show hint

    When different paths reach the same sub-question, such as the same remaining total, so answers can be reused.

What each operation costs: Depth First Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.