Introduction to backtracking
Backtracking is a general algorithmic technique that considers searching every possible combination in order to solve a problem.
- It is also known as depth-first search or branch and bound.
- It is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient (if not the most efficient) technique for parsing, for the knapsack problem and other combinatorial optimization problems.
- It usually takes an exponential time to solve the problem. However, dynamic programming and greedy algorithms can be thought of as optimizations to backtracking.
Backtracking Methodology :
- View picking a solution as a sequence of choices - For each choice, consider every option recursively - Return the best solution found
Some classic examples of using backtracking
1. Longest Common Subsequence (exhaustive version)
2. Shortest Path Problem (exhaustive version)
3. Largest Independent Set
4. Bounding Searches
5. Constrained 3-Coloring
6. Traveling Salesperson Problem
7. Generate all permutations of a given array