*879*

Backtracking is the method of exhaustive search using divide and conquer.

- Sometimes the best algorithm for a problem is to try all the possibilities.
- This is always slow, but there are standard tools that can be used for help.
- Tools: algorithms for generating basic objects, such as binary strings [2
^{n}possibilities for n-bit string], permutations [n!], combinations [n!/r!(n-r)!], general strings [k-ary strings of lengthÂ n has k^{n}possibilities], etc… - Backtracking speeds the exhaustive search by pruning.

### Example Algorithms of Backtracking

- Binary Strings: generating all binary strings
- Generating k-ary Strings.
- The knapsack problem
- Generalized Strings
- Hamiltonian Cycles
- Graph coloring problem

Code Samples: