What's the difference between backtracking and depth first search?

What's the difference between backtracking and depth first search?

Backtracking is a more general purpose algorithm.

Depth-First search is a specific form of backtracking related to searching tree structures. From Wikipedia:

> 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.

It uses backtracking as part of its means of working with a tree, but is limited to a tree structure.

Backtracking, though, can be used on any type of structure where portions of the domain can be eliminated - whether or not it is a logical tree. The Wiki example uses a chessboard and a specific problem - you can look at a specific move, and eliminate it, then backtrack to the next possible move, eliminate it, etc.

I think this answer to another related question offers more insights.

For me, the difference between backtracking and DFS is that backtracking handles an implicit tree and DFS deals with an explicit one. This seems trivial, but it means a lot. When the search space of a problem is visited by backtracking, the implicit tree gets traversed and pruned in the middle of it. Yet for DFS, the tree/graph it deals with is explicitly constructed and unacceptable cases have already been thrown, i.e. pruned, away before any search is done.

So, backtracking is DFS for implicit tree, while DFS is backtracking without pruning.

IMHO, most of the answers are either largely imprecise and/or without any reference to verify. So let me share a very clear explanation with a reference.

First, DFS is a general graph traversal (and search) algorithm. So it can be applied to any graph (or even forest). Tree is a special kind of Graph, so DFS works for tree as well. In essence, let’s stop saying it works only for a tree, or the likes.

Based on [1], Backtracking is a special kind of DFS used mainly for space (memory) saving. The distinction that I’m about to mention may seem confusing since in Graph algorithms of such kind we’re so used to having adjacency list representations and using iterative pattern for visiting all immediate neighbors (for tree it is the immediate children) of a node, we often ignore that a bad implementation of get_all_immediate_neighbors may cause a difference in memory uses of the underlying algorithm.

Further, if a graph node has branching factor b, and diameter h (for a tree this is the tree height), if we store all immediate neighbors at each steps of visiting a node, memory requirements will be big-O(bh). However, if we take only a single (immediate) neighbor at a time and expand it, then the memory complexity reduces to big-O(h). While the former kind of implementation is termed as DFS, the latter kind is called Backtracking.

Now you see, if you’re working with high level languages, most likely you’re actually using Backtracking in the guise of DFS. Moreover, keeping track of visited nodes for a very large problem set could be really memory intensive; calling for a careful design of get_all_immediate_neighbors (or algorithms that can handle revisiting a node without getting into infinite loops).

[1] Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 3rd Ed

According to Donald Knuth, it's the same. Here is the link on his paper about Dancing Links algorithm, which is used to solve such "non-tree" problems as N-queens and Sudoku solver.

> Backtracking, also called depth-first search

Backtracking is usually implemented as DFS plus search pruning. You traverse search space tree depth-first constructing partial solutions along the way. Brute-force DFS can construct all search outcomes, even the ones, that do not make sense practically. This can be also very inefficient to construct all solutions (n! or 2^n). So in reality as you do DFS, you need to also prune partial solutions, which do not make sense in context of the actual task, and focus on the partial solutions, which can lead to valid optimal solutions. This is the actual backtracking technique - you discard partial solutions as early as possible, make a step back and try to find local optimum again.

Nothing stops to traverse search space tree using BFS and execute backtracking strategy along the way, but it doesn't make sense in practice because you would need to store search state layer by layer in the queue, and tree width grows exponentially to the height, so we would waste a lot of space very quickly. That's why trees are usually traversed using DFS. In this case search state is stored in the stack (call stack or explicit structure) and it can't exceed tree height.

Usually, a depth-first-search is a way of iterating through an actual graph/tree structure looking for a value, whereas backtracking is iterating through a problem space looking for a solution. Backtracking is a more general algorithm that doesn't necessarily even relate to trees.

DFS describes the way in which you want to explore or traverse a graph. It focuses on the concept of going as deep as possible given the choice.

Backtracking, while usually implemented via DFS, focuses more on the concept of pruning unpromising search subspaces as early as possible.

I would say, DFS is the special form of backtracking; backtracking is the general form of DFS.

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.

They carry the same idea in algorithmic aspect.

IMO, on any specific node of the backtracking, you try to depth firstly branching into each of its children, but before you branch into any of the child node, you need to "wipe out" previous child's state(this step is equivalent to back walk to the parent node). In other words, each siblings state should not impact each other.

On the contrary, during normal DFS algorithm, you don't usually have this constraint, you don't need to wipe out(back track) previous siblings state in order to construct next sibling node.

Depth first is an algorithm for traversing or searching a tree. See here. Backtracking is a much more broad term that is used whereever a solution candidate is formed and later discarded by backtracking to a former state. See here. Depth first search uses backtracking to search a branch first (solution candidate) and if not successful search the other branch(es).

Depth first search(DFS) and backtracking are different searching and traversing algorithms. DFS is more broad and is used in both graph and tree data structure while DFS is limited to tree. With that being said,it does not mean DFS can't be used in graph. It is used in graph as well but only produce spanning tree, a tree without loop(multiple edge starting and ending at same vertex). That is why it is limited to tree.
Now coming back to backtracking, DFS use backtracking algorithm in tree data structure so in tree, DFS and backtracking are similar.
Thus,we can say, they are in same in tree data structure whereas in graph data structure, they are not same.

Idea - Start from any point, check if its the desired endpoint, if yes then we found a solution else goes to all next possible positions and if we can't go further then return to the previous position and look for other alternatives marking that current path wont lead us to the solution.

Now backtracking and DFS are 2 different names given to the same idea applied on 2 different abstract data types.

If the idea is applied on matrix data structure we call it backtracking.

If the same idea is applied on tree or graph then we call it DFS.

The cliche here is that a matrix could be converted to a graph and a graph could be transformed to a matrix. So, we actually apply the idea. If on a graph then we call it DFS and if on a matrix then we call it backtracking.

The idea in both of the algorithm is same.

In a depth-first search, you start at the root of the tree and then explore as far along each branch, then you backtrack to each subsequent parent node and traverse it's children

Backtracking is a generalised term for starting at the end of a goal, and incrementally moving backwards, gradually building a solution.

Backtracking is just depth first search with specific termination conditions.

Consider walking through a maze where for each step you make a decision, that decision is a call to the call stack (which conducts your depth first search)... if you reach the end, you can return your path. However, if you reach a deadend, you want to return out of a certain decision, in essence returning out of a function on your call stack.

So when I think of backtracking I care about

1. State
2. Decisions
3. Base Cases (Termination Conditions)

I explain it in my video on backtracking here.

An analysis of backtracking code is below. In this backtracking code I want all of the combinations that will result in a certain sum or target. Therefore, I have 3 decisions which make calls to my call stack, at each decision I either can pick a number as part of my path to reach the target num, skip that number, or pick it and pick it again. And then if I reach a termination condition, my backtracking step is just to return. Returning is the backtracking step because it gets out of that call on the call stack.

class Solution:    

"""

Approach: Backtracking 

State
    -candidates 
    -index 
    -target 

Decisions
    -pick one --> call func changing state: index + 1, target - candidates[index], path + [candidates[index]]
    -pick one again --> call func changing state: index, target - candidates[index], path + [candidates[index]]
    -skip one --> call func changing state: index + 1, target, path

Base Cases (Termination Conditions)
    -if target == 0 and path not in ret
        append path to ret
    -if target < 0: 
        return # backtrack 

"""

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    """
    @desc find all unique combos summing to target
    @args
        @arg1 candidates, list of ints
        @arg2 target, an int
    @ret ret, list of lists 
    """
    if not candidates or min(candidates) > target: return []
    
    ret = []
    self.dfs(candidates, 0, target, [], ret)
    return ret 

def dfs(self, nums, index, target, path, ret):
    if target == 0 and path not in ret: 
        ret.append(path)
        return #backtracking 
    elif target < 0 or index >= len(nums): 
        return #backtracking 
    
    
    # for i in range(index, len(nums)): 
    #     self.dfs(nums, i, target-nums[i], path+[nums[i]], ret)
    
    pick_one = self.dfs(nums, index + 1, target - nums[index], path + [nums[index]], ret)
    pick_one_again = self.dfs(nums, index, target - nums[index], path + [nums[index]], ret)
    skip_one = self.dfs(nums, index + 1, target, path, ret)

In my opinion, the difference is pruning of tree. Backtracking can stop (finish) searching certain branch in the middle by checking the given conditions (if the condition is not met). However, in DFS, you have to reach to the leaf node of the branch to figure out if the condition is met or not, so you cannot stop searching certain branch until you reach to its leaf nodes.

The way I look at DFS vs. Backtracking is that backtracking is much more powerful. DFS helps me answer whether a node exists in a tree, while backtracking can help me answer all paths between 2 nodes.

Note the difference: DFS visits a node and marks it as visited since we are primarily searching, so seeing things once is sufficient. Backtracking visits a node multiple times as it's a course correction, hence the name backtracking.

Most backtracking problems involve:

def dfs(node, visited):
  visited.add(node)
  for child in node.children:
    dfs(child, visited)
  visited.remove(node) # this is the key difference that enables course correction and makes your dfs a backtracking recursion.