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.

**Backtracking Pseudocode**

A pseudocode for the above question would be :

```
boolean pathFound(Position p) {
if (p is finish) return true;
foreach option O from p {
boolean isThereAPath = pathFound(O);
if (isThereAPath) return true; // We found a path using option O
}
// We have tried all options from this position and none of the options lead to finish.
// Hence there is no solution possible to finish
return false;
}
```

In general, the usual pseudocode for any backtracking solution is :

```
boolean solve(Node n) {
if n is a goal node, return true
foreach option O possible from n {
if solve(O) succeeds, return true
}
return false
}
```

Now, head over to the assignments, and try out some of the problems. Most of them involve backtracking.