# Backtracking Notes đ„

Reference:

- Wikipedia - Backtracking
- GeeksforGeeks - Backtracking
- Whatâs the difference between backtracking and depth first search?
- difference between back tracking and Dynamic programming

## Definition

**Wiki:** Backtracking is a general algorithm for finding all (or some) solutions to some `computational problems`

, notably `constraint satisfaction problems`

, that **incrementally** builds candidates to the solutions, and abandons a candidate (âbacktracksâ) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

**GeeksforGeeks:** Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, **one piece at a time**, removing those solutions that fail to satisfy the constraints of the problem `at any point of time`

(by time, here, is referred to the time elapsed till reaching any level of the search tree).

Notice the difference between âbacktrackingâ and âbacktracksâ. The latter one is more like `delete`

or `remove`

a candidate or a selection.

## Backtracking vs. DFS

`Backtracking`

is a more**general**purpose algorithm. It iterates through a**problem space**. It can be used on any type of structure where portions of the domain can be eliminated, that is, you can look at a specific move and eliminate it.`Depth-First search`

is a**specific**form of backtracking related to searching tree or graph structures. It iterates through an actual**tree/graph structure**. DFS is described in Wikipedia as follows:

One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

If we extend DFS to general problems, we can call it `backtracking`

. If we use backtracking to tree/graph related problems, we can call it `DFS`

.

According to Donald Knuth, it is the same.

Backtracking, also called depth-first search. â His paper about Dancing Links algorithm

## Backtracking vs. DP

**Note:** I think they should not be compared since they are very different algorithmic approaches.

Dynamic programming problems usually rely on the

`principle of optimality`

. The principle of optimality states that an optimal sequence of decision or choices each sub sequence must also be optimal. Also, DP**breaks down**the problem into many smaller overlapped subproblems.Backtracking problems are usually not optimal on their way. They can only be applied to problems which admit the concept of

`partial candidate solution`

. It does not include any âbreak downâ step, but builds the solution**incrementally**.