Theory
Backtracking builds a solution incrementally. When a choice cannot lead to a valid solution, the algorithm removes that choice and tries another possibility. Backtracking is commonly used for N-Queens, Sudoku, permutations and combinations.
Example
function generate(index, current, result) {
if (index === 3) {
result.push([...current]);
return;
}
for (let value = 0; value <= 1; value++) {
current.push(value);
generate(index + 1, current, result);
current.pop();
}
}
const result = [];
generate(0, [], result);
console.log(result);
Expected Output
All valid binary combinations of length 3 are generated.
Practice
Generate all permutations of a small array using backtracking.
Interview Questions
- What is backtracking?
- Why do we undo a choice?
- Where is backtracking used?
- How is backtracking related to recursion?