# 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