Backtracking

The Central Idea

A backtracking algorithm repeatedly follows this pattern:

1. make a choice;
2. extend the current partial solution;
3. check whether the partial solution is still valid or promising;
4. continue if it is;
5. otherwise undo the choice and try another alternative.

The essential action is the ability to backtrack.

Backtracking Explores a Search Space

The search space contains the possible complete solutions.

Instead of generating every complete possibility immediately, backtracking builds solutions incrementally.

Each partial solution represents a point in the search process.

Decision Trees

Backtracking is naturally represented by a decision tree.

Each node represents a partial solution.

Each outgoing edge represents one available next choice.

Leaves may represent:

• complete valid solutions;
• complete invalid solutions;
• dead ends discovered before completion.

A Simple Binary Choice Tree

Suppose three objects may each be either selected or not selected.

For each object, the algorithm has two choices:

or

The resulting search tree has up to

complete leaves.

Partial Solutions

A partial solution contains choices made so far but is not yet complete.

For a permutation problem, it may be a prefix such as

For a path problem, it may be a route such as

For a subset problem, it may record which first few items have been included.

Constraint Checks

A backtracking algorithm should test whether the current partial solution violates any constraint.

If a violation has already occurred, there is no reason to continue deeper along that branch.

This early rejection is called pruning.

Pruning

Pruning removes a branch of the search tree because that branch cannot lead to a useful complete solution.

Pruning can save enormous amounts of work.

The central question is:

Can we prove that every completion of this partial choice will fail or be irrelevant?

Undoing a Choice

When a branch fails, the algorithm restores the earlier state.

For example:

1. add candidate \(x\);
2. explore recursively;
3. remove candidate \(x\);
4. try the next candidate.

The add–explore–remove pattern is a standard form of backtracking.

Backtracking Is Often Recursive

Recursion is a natural implementation because each recursive call represents a deeper partial solution.

When a call returns, the algorithm automatically moves back to an earlier decision level.

The program call stack mirrors the search tree.

A General Backtracking Pattern

A conceptual backtracking procedure is:

1. If the current partial solution is complete, record or return it.
2. Otherwise, list the available next choices.
3. For each choice, test whether it is allowed.
4. Make the choice.
5. Recurse on the extended partial solution.
6. Undo the choice.

Generating Permutations

Backtracking can generate all permutations of a finite set.

Suppose we want all permutations of

The first position may contain \(A\), \(B\), or \(C\).

After choosing one symbol, recursively permute the unused symbols.

Permutation Search Tree

If the first choice is \(A\), the remaining possibilities are

or

The same reasoning applies after first choosing \(B\) or \(C\).

The complete permutations are

Why Used-Item Tracking Matters

In a permutation, each item may be used exactly once.

Therefore, the algorithm must know which items have already been placed.

A typical constraint check is:

Do not choose an item that is already used in the current partial permutation.

Generating Subsets

Backtracking can also generate subsets.

For each item, choose either:

or

With \(n\) independent binary choices, there are

possible subsets.

Subset Sum

In the subset-sum problem, we ask whether some subset of given numbers has a specified target sum.

For example, given

and target

one valid subset is

Backtracking for Subset Sum

At each item, the search can branch:

• include the item;
• exclude the item.

The algorithm tracks the current sum.

If the target is reached, success can be reported.

Pruning Subset Sum

Suppose all remaining numbers are positive.

If the current sum already exceeds the target, then adding more positive values can never repair the branch.

Therefore, that branch can be pruned immediately.

Mazes and Paths

A maze can be viewed as a state-space graph.

A backtracking solver:

1. moves to an available neighboring position;
2. marks or records the move;
3. continues recursively;
4. backs up when it reaches a dead end.

This is closely related to depth-first search.

Backtracking and Depth-First Search

Both methods explore one branch deeply before trying alternatives.

Depth-first search is usually framed as traversing an existing graph.

Backtracking is usually framed as constructing and testing candidate solutions in a search space.

Their implementation patterns often overlap.

Avoiding Cycles in Path Search

If a path search may revisit the same location indefinitely, the algorithm should record the positions already used in the current path.

A common rule is:

Do not move to a vertex already on the current path.

When backtracking leaves a vertex, that mark may be removed if the same vertex is allowed in a different candidate path.

Current-Path Marks Versus Permanent Visited Marks

Backtracking sometimes needs a different notion of "visited" from ordinary graph traversal.

In DFS reachability, a vertex may be permanently marked once discovered.

In a path-construction problem, a vertex might be forbidden only within the current partial path and become available again after backtracking.

Constraint Satisfaction Problems

Backtracking is a standard method for constraint satisfaction problems.

These problems contain:

• variables;
• possible values for each variable;
• constraints restricting compatible assignments.

The algorithm assigns values incrementally and rejects inconsistent partial assignments.

Graph Coloring as Backtracking

Suppose each vertex of a graph must receive one of \(k\) colors so that adjacent vertices have different colors.

A backtracking algorithm may:

1. choose an uncolored vertex;
2. try an available color;
3. check whether any adjacent colored vertex conflicts;
4. continue if valid;
5. otherwise undo the color and try another.

Early Constraint Checks Matter

If two adjacent vertices already have the same color, the current partial coloring is invalid.

There is no reason to color the remaining vertices.

Immediate rejection prevents the algorithm from exploring an entire invalid subtree.

N-Queens Intuition

In the \(n\)-queens problem, \(n\) queens must be placed on an \(n\times n\) chessboard so that no two queens attack each other.

One backtracking strategy places queens row by row.

Before placing a queen, test whether its column or diagonals conflict with earlier queens.

Why Row-by-Row Placement Helps

If exactly one queen is placed in each row, row conflicts are eliminated automatically.

The remaining checks involve:

• columns;
• main diagonals;
• opposite diagonals.

Good problem representation can simplify the backtracking constraints.

Choice Ordering

The order in which choices are tried does not usually affect whether a complete exhaustive backtracking algorithm is correct.

But it can greatly affect how quickly a solution is found.

Trying promising choices first can reduce practical search time.

Variable Ordering

In constraint problems, the order in which variables are assigned may also matter.

A useful heuristic is to handle the most constrained variable early.

This can expose contradictions sooner and enable earlier pruning.

Heuristics Do Not Replace Correctness

A heuristic may change search order without changing the set of branches that remain eligible.

If the algorithm still explores every unpruned valid possibility, the heuristic affects performance rather than correctness.

Unsafe pruning, however, can destroy correctness.

Safe Pruning

A pruning rule is safe if every branch it removes is known to contain no valid or relevant solution.

The proof obligation is important:

Why can this branch be discarded without losing a solution that matters?

Optimization with Backtracking

Backtracking can search for the best solution, not merely any valid solution.

The algorithm may track the best complete solution found so far.

Partial branches can sometimes be pruned when they cannot possibly improve on the current best.

Bounds

A bound estimates the best result a partial branch could still achieve.

If even that optimistic estimate is worse than the best known complete solution, the branch can be discarded.

This idea leads toward branch-and-bound methods.

Backtracking Versus Brute Force

Brute force may generate every complete candidate and test each one.

Backtracking improves on this by testing partial candidates early.

When a partial candidate already fails, all of its possible completions can be skipped.

Backtracking Versus Greedy Methods

A greedy method usually commits permanently to one locally attractive choice.

Backtracking tries a choice provisionally.

If that choice leads to failure, it is undone and another alternative is explored.

Backtracking Versus Dynamic Programming

Backtracking is organized around alternative choices and search branches.

Dynamic programming is organized around distinct states whose answers can be stored and reused.

The two methods can sometimes be combined when many backtracking branches lead to the same remaining state.

Backtracking Versus Divide and Conquer

Divide and conquer splits a problem into subproblems that are all needed for the final result.

Backtracking explores alternatives, many of which may be rejected.

Divide and conquer decomposes required work; backtracking searches among possible choices.

Completeness

A backtracking algorithm is complete if it eventually examines every candidate branch that could contain a valid solution, unless that branch is safely pruned.

If a solution exists and no valid branch is incorrectly removed, complete backtracking will eventually find one.

Termination

Backtracking terminates on a finite search tree if every recursive step moves to a deeper partial solution and every branch has bounded depth.

Once all choices at a node have been tried, the call returns.

Eventually, every reachable branch is either completed or pruned.

Worst-Case Growth

Backtracking can still require enormous time.

If each of \(n\) stages has two possibilities, the complete search tree may contain on the order of

leaves.

For permutations, the number of complete possibilities can grow as

Pruning Changes Practical Performance

The theoretical worst case may remain exponential or factorial even when pruning is used.

However, effective pruning can make real instances dramatically smaller by cutting off large invalid regions of the search tree.

Backtracking State

A recursive backtracking call typically needs enough information to describe the current partial solution.

This state may include:

• the current position or depth;
• choices already made;
• used items;
• current totals or costs;
• constraint information.

State Restoration

After exploring one choice, the algorithm must restore the state exactly to what it was before that choice.

Otherwise, information from one branch may incorrectly affect another branch.

Correct undo operations are therefore essential.

Copying State Versus Modifying and Undoing

One implementation can create a fresh copy of the partial state for each recursive branch.

Another can modify one shared state, recurse, and then undo the modification.

Copying can simplify reasoning but may use more memory.

Modify-and-undo can be efficient but demands careful restoration.

Stopping After One Solution

Some problems ask only whether a solution exists or request any one solution.

In that case, the search may stop as soon as a valid complete solution is found.

This can avoid exploring the rest of the search tree.

Finding All Solutions

Other problems require every valid solution.

Then finding one solution is not enough.

The algorithm records the solution, backtracks, and continues exploring remaining branches.

Counting Solutions

Backtracking can also count valid complete assignments.

Each valid leaf contributes

to the count.

Invalid or pruned branches contribute

Common Error: Forgetting to Undo

Suppose an item is added to a partial solution, one recursive branch is explored, and the item is never removed afterward.

The next branch begins with incorrect state.

This is one of the most common implementation errors in backtracking.

Common Error: Pruning Too Aggressively

A branch should be removed only when it is certain that the branch cannot produce a needed solution.

A merely unattractive or unlikely branch may still contain the optimum.

Unsafe pruning can make an algorithm fast but wrong.

Common Error: Failing to Prune Obvious Contradictions

The opposite mistake is continuing after a partial solution has already violated a constraint.

This does not necessarily destroy correctness, but it wastes time exploring branches that can never succeed.

Common Error: Treating Current-Path Marks as Permanent

In some path-construction problems, a vertex used in one candidate path may still be valid in a different candidate path.

If the mark is never removed during backtracking, legitimate solutions may be lost.

Common Error: Returning Too Early

If the task is to find all solutions, returning after the first valid leaf is incorrect.

The stopping rule must match the required output:

• one solution;
• all solutions;
• number of solutions;
• best solution.

Common Error: Confusing Backtracking with Random Trial

Backtracking follows a systematic search rule.

It records the current state, explores choices, and returns to earlier decisions in a controlled way.

Random guessing does not provide the same completeness guarantee.

A Reliable Procedure for Designing Backtracking

1. Define what a complete solution looks like.
2. Define what information belongs in a partial solution.
3. Identify the possible next choices.
4. State the constraints that partial solutions must satisfy.
5. Write a safe pruning test.
6. Choose a recursive stopping condition.
7. Make one choice.
8. Update the state.
9. Recurse.
10. Undo the choice exactly.
11. Continue until the required solution set is obtained.

Example: Permutations of Three Symbols

Begin with

Choose \(A\) first.

Then recursively choose among

This gives

Backtrack to the first position and continue with \(B\), then \(C\).

Example: Subset Target

Consider

with target

One branch includes \(2\), then \(4\), then tests whether further additions can reach \(11\).

Another branch includes \(2\) and \(9\), producing

Example: Simple Path Search

Suppose a graph has edges

To find simple paths from \(A\) to \(D\), backtracking can explore

and then backtrack to explore

Current-path marking prevents repeated vertices within a candidate path.

Practice 1: Core Pattern

What is the defining action that distinguishes backtracking from a greedy method?

Practice 2: Decision Tree

If four independent items may each be either included or excluded, how many complete include/exclude assignments are possible?

Practice 3: Permutations

How many complete permutations are possible for

Practice 4: Safe Pruning

In subset sum with only positive numbers, why can a branch be pruned when the current sum already exceeds the target?

Practice 5: Undoing State

Why must a backtracking algorithm remove a choice after returning from the recursive call that explored that choice?

Practice 6: Graph Coloring

When coloring a vertex, what immediate condition should cause the current color choice to be rejected?

Practice 7: One Solution Versus All Solutions

How should the search behavior differ when the task asks for all valid solutions rather than any one valid solution?

Practice 8: Current Path

In a simple-path problem, why might a vertex mark need to be removed when the algorithm backtracks?

Practice 9: Worst-Case Size

A backtracking problem has \(n\) independent binary choices and no useful pruning.

Approximately how many complete candidates may need to be examined?

Practice 10: Classify the Strategy

An algorithm chooses a value for a variable, later detects a contradiction, restores the previous state, and tries another value.

What algorithmic strategy is being used?

Practice Answers

Practice 1

Backtracking can

Practice 2

Each of four items has two choices, so there are

complete assignments.

Practice 3

Practice 4

Because every remaining number is positive, any further inclusion can only increase the sum. Once the current sum is above the target, that branch can never return to the target.

Practice 5

The state must be restored so the next branch begins from the same earlier partial solution rather than inheriting a choice that belongs to a different branch.

Practice 6

Reject the color if an already colored adjacent vertex has the same color.

Practice 7

For one solution, the algorithm may stop after the first valid complete candidate is found. For all solutions, it must record that solution, backtrack, and continue exploring all remaining eligible branches.

Practice 8

The vertex may be valid in another candidate path. Removing the current-path mark allows the algorithm to reuse that vertex in a different branch while still preventing cycles within one partial path.

Practice 9

Practice 10

What to Remember

• Backtracking builds partial solutions and explores alternatives systematically.
• When a choice leads to failure, the algorithm restores the earlier state and tries another choice.
• Decision trees provide a natural model of the search process.
• Pruning removes branches that cannot contain a needed solution.
• Pruning must be safe; otherwise valid solutions can be lost.
• Backtracking is useful for permutations, subsets, paths, coloring, puzzles, and constraint problems.
• Choice ordering can strongly affect practical performance.
• Worst-case search may still grow exponentially or factorially.
• Correct state restoration is essential.

The most important habit is to ask: What choices can I make next, and how soon can I prove that a partial choice can no longer lead to a valid solution?

Where We Go Next

Backtracking explores a branching search space by trying and undoing choices. Many important computational problems are organized directly on graphs and networks, where traversal, connectivity, spanning structures, and path methods can be expressed as specialized algorithms.

The next lesson, Graph Algorithms, develops core algorithmic procedures for graph traversal, connectivity, spanning trees, shortest paths, and related network computations.