Why is this called backtracking?

java algorithm backtracking
Elad Benda2 picture Elad Benda2 · Jun 23, 2014 · Viewed 14.5k times · Source

I have read in Wikipedia and have also Googled it,

but I cannot figure out what "Backtracking Algorithm" means.

I saw this solution from "Cracking the Code Interviews"

and wonder why is this a backtracking algorithm?

enter image description here

Answer

Josef E. picture Josef E. · Jun 23, 2014

Backtracking is a form of recursion, at times.

This boolean based algorithm is being faced with a choice, then making that choice and then being presented with a new set of choices after that initial choice.

Conceptually, you start at the root of a tree; the tree probably has some good leaves and some bad leaves, though it may be that the leaves are all good or all bad. You want to get to a good leaf. At each node, beginning with the root, you choose one of its children to move to, and you keep this up until you get to a leaf.(See image below)

enter image description here

Explanation of Example:

  1. Starting at Root, your options are A and B. You choose A.
  2. At A, your options are C and D. You choose C.
  3. C is bad. Go back to A.
  4. At A, you have already tried C, and it failed. Try D.
  5. D is bad. Go back to A.
  6. At A, you have no options left to try. Go back to Root.
  7. At Root, you have already tried A. Try B.
  8. At B, your options are E and F. Try E.
  9. E is good. Congratulations!

Source: upenn.edu

Related questions

Given n and k, return the kth permutation sequence

The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3 ) : "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence. For example, given …

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Generating all permutations of a given string

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

Read More