What is Backtracking?

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

1. Generate all the strings of n bits.