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 [2n possibilities for n-bit string], permutations [n!], combinations [n!/r!(n-r)!], general strings [k-ary strings of length n has kn 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