5. Pruning
- Why pruning is essential
- How constraints reduce the search space
- Early vs late pruning
- Bounding and optimization
- Impact on time complexity
Backtracking without pruning is often impractical.
The search tree grows exponentially, and exploring all branches quickly becomes infeasible.
Pruning is what makes backtracking efficient.
5.1 Why Pruning Matters
In many problems, the full search tree is enormous.
However, most branches do not lead to valid solutions.
Pruning allows the algorithm to skip entire subtrees that cannot produce a valid solution.
5.2 Constraint-Based Pruning
The most basic form of pruning comes from constraints.
If a partial solution violates constraints, we stop exploring immediately.
This is called early pruning.
5.3 Early vs Late Pruning
Pruning can happen at different stages:
- Early pruning: reject as soon as possible
- Late pruning: reject after deeper exploration
5.4 Bounding (Optimization Problems)
In optimization problems, we can prune using bounds.
If a partial solution cannot beat the best known solution, it can be discarded.
This idea is the foundation of Branch and Bound.
5.5 Impact on Complexity
In theory, backtracking is exponential.
But with effective pruning, the actual number of explored nodes can be dramatically smaller.
- Worst case: exponential
- With pruning: often much faster in practice
5.6 Intuition
Without pruning:
explore everything → slow
With pruning:
explore only promising paths → fast
5.7 Summary
- Pruning eliminates useless branches
- Constraints enable early pruning
- Bounds enable optimization pruning
- Efficiency depends heavily on pruning quality
Next: Part 6 — Classic Problems
Now that we understand how backtracking works and how to make it efficient, we can study real problems.
In Part 6, we apply backtracking to classical problems such as N-Queens, permutations, and graph problems.