Backtracking is trying out all possibilities using recursion, exactly like bruteforce.
Suppose you have to make a series of decisions, among various choices, where :
* You don’t have enough information to know what to choose * Each decision leads to a new set of choices * Some sequence of choices (possibly more than one) may be a solution to your problem
Backtracking is a methodical way of trying out various sequences of decisions, until you find one that “works”.
Lets look at an example to explain this further.
Given a maze, find if a path from start to finish
At each intersection, you have to decide between three or fewer choices:
* Go straight * Go left * Go right
You don’t have enough information to choose correctly. Each choice leads to another set of choices. One or more sequences of choices may (or may not) lead to a solution.
So, you explore each option thoroughly and once you cannot find a solution using the option selected, you come back and try one of the remaining options.