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.

Backtracking can be applied only for problems which admit the concept of a “partial candidate solution” and a relatively quick test of whether it can possibly be completed to a valid solution. Backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.

In this post, we have list out common problems that can be solved using backtracking technique –

- Print all possible solutions to N Queens problem

- Print all Possible Knight’s Tours in a chessboard

- Find Shortest Path in Maze

- Find Longest Possible Route in a Matrix

- Find path from source to destination in a matrix that satisfies given constraints

- Find total number of unique paths in a maze from source to destination

- Print All Hamiltonian Path present in a graph

- Print all k-colorable configurations of the graph (Vertex coloring of graph)

- Find all Permutations of a given string

- All combinations of elements satisfying given constraints

- Find all binary strings that can be formed from given wildcard pattern

- K-Partition Problem | Printing all Partitions

- Magnet Puzzle

- Find ways to calculate a target from elements of specified array

- Find minimum number possible by doing at-most K swaps

- Determine if a pattern matches with a string or not

**Thank you for being with us. 🙂**

## Leave a Reply