What is backtracking? | Interview Question

Q: What is backtracking?

**Target Audience:** Beginners preparing for coding interviews — you should know what a function call and recursion are **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First You are in a hedge maze with a piece of chalk. At every fork you pick a path and walk on. When you hit a dead end you do not teleport back to the entrance — you walk back to the **last fork** where an untried path is left, chalk off the one you just tried, and take the next. Eventually you have either found the exit or tried everything. Now imagine some paths have a sign at their entrance

The problem

Question presented to candidate: "Explain what backtracking is, how it differs from plain brute force, and show me the pattern on a small problem in Python."

What a strong answer should cover:

The idea: build a solution one decision at a time, and undo the last decision when it cannot lead to an answer, then try the next option.
The three-step pattern choose / explore / un-choose, and the base case that records a complete solution.
Pruning: checking constraints before recursing, and why it is the difference between backtracking and brute force.
The state-space tree picture, and complexity as (number of nodes) × (work per node), usually exponential; space is the recursion depth.
Python details: one shared list as the path with append/pop, recording a copy (path[:] or "".join(path)), and the default recursion limit of 1000 frames that caps the depth.

Code / implementation expected: Optional — a short recursive generator in Python (for example generate parentheses) that shows choose / explore / un-choose and one pruning rule.

backtracking

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know what a function call and recursion are
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

You are in a hedge maze with a piece of chalk. At every fork you pick a path and walk on. When you hit a dead end you do not teleport back to the entrance — you walk back to the last fork where an untried path is left, chalk off the one you just tried, and take the next. Eventually you h

The solution is hidden so you can try first

10 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonGenerate parentheses: brute force vs backtracking (call counts)

Practice

PythonTrace every choose, prune and undo for n = 2

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.