DSA · Patterns, not puzzles
How does backtracking work?
Short answer
Backtracking explores a decision tree depth-first, undoing each choice when a path cannot lead to a valid solution. It is suited to constraint problems such as subsets, permutations, combinations and board search.
Backtracking is recursion with a state that you modify, recurse into, then restore. The restore step is what lets the same state object explore sibling branches. Pruning invalid or hopeless branches early is what separates an acceptable solution from an exponential brute force.
function subsets(values) {
const result = [];
const current = [];
function explore(index) {
if (index === values.length) {
result.push([...current]);
return;
}
explore(index + 1);
current.push(values[index]);
explore(index + 1);
current.pop();
}
explore(0);
return result;
}The general template
- Choose: add a candidate to the current state
- Explore: recurse with the updated state
- Unchoose: remove the candidate before the next branch
- Prune: stop early when the state cannot satisfy the constraints
- Collect: record a copy of the state when a complete solution is found
function permute(values) {
const result = [];
const used = new Array(values.length).fill(false);
const current = [];
function explore() {
if (current.length === values.length) {
result.push([...current]);
return;
}
for (let i = 0; i < values.length; i++) {
if (used[i]) continue;
used[i] = true;
current.push(values[i]);
explore();
current.pop();
used[i] = false;
}
}
explore();
return result;
}Follow-ups you should expect
Interviewers use these to check whether the first answer was understanding or memorisation.
- 1Why do you need to undo a choice after recursing?
- 2How do you prune duplicate permutations?
- 3What is the time complexity of generating all subsets?
- 4How would you solve N-Queens with backtracking?
Say it in the interview
Backtracking explores choices depth-first by adding a candidate, recursing, then removing it so the next branch starts from the same state. If a partial state cannot satisfy the constraints, I return early and prune that subtree. The key details are restoring state correctly and pushing a copy when I record a solution, because without pruning the worst case is exponential.
Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.
Related questions
Reading is step one
Now say it out loud.
Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.