Reference:

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.