# Backtracking Algorithm

**Backtracking** is a general algorithmic technique that considers searching every possible combination in order to solve an optimization problem. Backtracking is also known as **depth-first search** or **branch and bound**. While backtracking is useful for hard problems to which we do not know more efficient solutions, it is a poor solution for the everyday problems that other techniques are much better at solving.

However, dynamic programming and greedy algorithms can be thought of as optimizations to backtracking, so the general technique behind backtracking is useful for understanding these more advanced concepts. Learning and understanding backtracking techniques first provides a good stepping stone to these more advanced techniques because you won’t have to learn several new concepts all at once.

steps to follow ::

for example,

- Starting at Root, your options are A and B. You choose A.
- At A, your options are C and D. You choose C.
- C is bad. Go back to A.
- At A, you have already tried C, and it failed. Try D.
- D is bad. Go back to A.
- At A, you have no options left to try. Go back to Root.
- At Root, you have already tried A. Try B.
- At B, your options are E and F. Try E.
- E is good. Congratulations!

**The backtracking algorithm.**

Here is the algorithm (in pseudocode) for doing backtracking from a given node n:

boolean solve(Node n) { if n is a leaf node { if the leaf is a goal node, return true else return false } else { for each child c of n { if solve(c) succeeds, return true } return false } }