Home Theory What is Backtracking?

What is Backtracking?

by nikoo28
0 comment 1 minutes read

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

Code Samples:

  1. Generate all the strings of n bits.

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More