DSA Lesson 28 of 33

Backtracking

Learn how to explore possible solutions and undo choices when needed.

Course Progress85%

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

  1. What is backtracking?
  2. Why do we undo a choice?
  3. Where is backtracking used?
  4. How is backtracking related to recursion?