liveBook · Manning

Backtracking

As explained in Algorithms Every Programmer Should Know

Search backtracking returns to an earlier search state after exploring one branch so that other branches can be examined.

Suppose you are looking for groups of people who all know one another. You grow a group one person at a time. When no one else can join, you return to an earlier choice and try a different person. That return is backtracking: it lets a search explore another branch without starting the entire problem over. section 11.0

In the Bron–Kerbosch algorithm, three sets make the search precise: R holds the clique being built, P holds vertices still eligible to join it, and X holds vertices already explored. To try a vertex from P, add it to R and intersect P and X with its neighbors. After exploring that branch, move the vertex from P to X and try another. section 11.1

What happens when a branch runs out of candidates?

  • If P and X are both empty, report R: it is a maximal clique. section 11.1
  • If P is empty but X is not, backtrack without reporting R; an already explored vertex shows this group is not a new maximal clique. section 11.1

Returning to a choice

One branch grows R to {1, 2, 4} and reports it. The search then unwinds and tries another branch, keeping vertex 1 in X. A later branch reaches {2, 4} with no candidates left, but vertex 1 remains in X, so it reports nothing. Trying further choices finds {2, 3, 5} as another maximal clique. section 11.1

Figure 11.4 Backtracking to the top level and starting the second branch. With the {1, 2, 4} branch closed out, the recursion unwinds to the root call and tries vertex 2 next. Vertex 1 already fully explored moves into X instead of disappearing, and the new P and X are computed by intersecting the old sets with vertex 2's neighbors, so only vertices still compatible with the growing clique carry forward.

Follow the return to the top-level call: an explored vertex moves into X while the next branch gets its own eligible candidates. section 11.1

Backtracking is not automatically fast. Enumerating every vertex subset to test for cliques costs O(n² × 2ⁿ) in the stated brute-force approach. Bron–Kerbosch narrows candidates as it searches; pivoting further reduces the branches considered. The word can also describe a *costly* return: naive string matching moves a text pointer backward after a mismatch and rechecks characters. KMP avoids that repeated work. Ask what state a search preserves when it backs up. section 11.1 section 5.0

How Algorithms Every Programmer Should Know covers it

How deep it goes
Traces recursive state changes and reporting rules for maximal cliques, but treats string-search backtracking chiefly as a bottleneck.
Examples
Traces clique branches {1, 2, 4} and {2, 3, 5}, alongside the repetitive-pattern search for AAAAAB.
What it assumes
Defines cliques and maximal cliques before the graph walkthrough and recalls Big-O when discussing naive string search.
What you can do after
Build it from scratch as a recursive Python maximal-clique search that filters candidates and avoids reporting previously explored cliques.
How it connects
Connects recursion, maximal cliques, set intersection, duplicate avoidance, pivoting, naive string matching, and the Knuth–Morris–Pratt algorithm.

Also explained in

Compare how 9 books explain backtracking →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.