Logic behind it
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems
, that incrementally builds candidates to the solutions, and abandons each partial candidate c (“backtracks”) as soon as it determines that c cannot possibly be completed to a valid solution.
The backtracking algorithm enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps.
Conceptually, the partial candidates are represented as the nodes of a tree structure, the potential search tree. The backtracking algorithm traverses this search tree recursively, from the root down, in depthfirst order. At each node c, the algorithm checks whether c can be completed to a valid solution. If it cannot, the whole subtree rooted at c is skipped (pruned). Otherwise, the algorithm: checks whether c itself is a valid solution, and if so reports it to the user; recursively enumerates all subtrees of c.
The tests and the children of each node are defined by usergiven procedures. Therefore, the actual search tree that is traversed by the algorithm is only a part of the potential tree. The total cost of the algorithm is the number of nodes of the actual tree times the cost of obtaining and processing each node.
This fact should be considered when choosing the potential search tree
and implementing the pruning
test.
Generalized Algorithm


Typical problems
Combination Sum III, Restore IP Addresses, Word Break II, NQueens, Sudoku Solver, more