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








