Interview OS
Back to Algorithms & Data Structures

Library

Backtracking

Choose, explore, un-choose.

Search

Overview

Backtracking systematically explores the space of partial solutions, pruning branches that violate constraints. It's the general engine for combinatorial search: permutations, subsets, N-Queens, and Sudoku.

How it works

Search
ChooseExplorePruneOutputCandidateplaceRecursedfsBoundvalid?Solutions
ClientServiceEdgeData

Step by step, with examples

  1. 1

    Candidate

    • Try one option.
  2. 2

    Recurse

    • Deepen with that choice.
  3. 3

    Bound

    • Cut invalid branches early.
  4. 4

    Solutions

    • Undo and continue searching.
    • Example: N-Queens

Overview

Build candidates incrementally and abandon partial solutions that can't succeed.

When to use it

  • Permutations/combinations
  • N-Queens / Sudoku
  • Constraint satisfaction

Common pitfalls

  • Forgetting to undo state
  • No pruning -> exponential blowup

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides