Backtracking ensures correctness by enumerating all possibilities. For example, a correct algorithm to find the optimal traveling salesman tour could enumerate all n! permutations of n vertices of the graph and selecting the best one. For each permutation, we could check whether each of the n edges implied in the tour really exists in the graph G, and if so, sum the weights of these edges together.
For most graphs, however, it would be pointless to construct all the
permutations
first and then analyze them later.
Suppose we started our search from vertex 
, and it happened that
edge 
was not in G.
Enumerating all the (n-2)! permutations beginning with 
would be
a complete waste of effort.
Much better would be to prune the search after and continue next
with 
.
By carefully restricting the set of next elements to reflect only the moves
that are legal from the current partial configuration, we reduce the
search complexity significantly.
Pruning is the technique of cutting off search the instant we have
established that this partial solution cannot be extended into the solution
that we want.
For example, in our traveling salesman search program, we seek the cheapest
tour that visits all vertices before returning to its starting position.
Suppose that in the course of our search we find a tour t whose cost
is 
.
As the search continues, perhaps we will find a partial solution
, where k < n and the sum of the edges on this
partial tour is 
.
Can there be any reason to continue exploring this node any further?
No, assuming all edges have positive cost, because any tour with the
prefix will have cost greater than tour t, and
hence is doomed to be non-optimal.
Cutting away such failed partial tours as soon as possible can
have an enormous impact on running time.
Exploiting symmetry is a third avenue for reducing combinatorial search.
It is clearly wasteful to evaluate the same candidate solution more
than once, because we will get the exact same answer each time we consider it.
Pruning away partial solutions identical to those previously considered
requires recognizing underlying symmetries in the search space.
For example, consider the state of our search for an optimal TSP tour
after we have tried all partial positions beginning with .
Can it pay to continue the search with partial solutions beginning
with 
?
No. Any tour starting and ending at can be viewed as
starting and ending at or any other vertex,
for these tours are cycles.
There are thus only (n-1)! distinct tours on n vertices, not n!.
By restricting the first element of the tour to always be , we save
a factor of n in time without missing any interesting solutions.
Detecting such symmetries can be subtle, but once identified they can usually
be easily exploited by a search program.