# 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

References :

1. WikiBooks

2. Wiki