Skip to content
Essay · Craft

What is the difference between backtracking and DFS

The difference between backtracking and DFS comes down to three things: whether the tree already exists, whether state is undone on the way back, and whether branches are pruned. Worked numbers for permutations and eight queens show what each choice costs.

By Vishy10 min readPublished · 18 Nov 2026

The difference between backtracking and DFS is that DFS is a traversal order over a structure that already exists, while backtracking is a search strategy that builds candidates incrementally and abandons a partial one the moment it cannot succeed. Backtracking is usually DFS run over an implicit tree, plus an undo step and a pruning test.

I think the confusion is understandable, and I think it does damage. Textbooks present both as "go deep first, then come back", and the recursion skeleton looks almost identical. So people learn one template, paste it onto every problem, and then wonder why their word search returns wrong answers or why their permutation generator is still running after ten minutes. The two techniques answer different questions. The difference shows up in exactly three places: what the tree is made of, what happens to state on the way back up, and what you pay in time.

Is backtracking just DFS with extra steps?

Mostly yes, and the extra steps are the entire point. Backtracking walks a tree depth first, so structurally it is a DFS. What differs is what the tree is made of and what you do when you leave a node.

In a classic DFS the structure exists before you start. You are handed a graph, a grid, or a tree, with nodes and edges sitting in memory, and your job is to visit them in a particular order. Each node is visited at most once because you mark it and never look back. The cost is O(V + E), and that bound is why DFS is trusted on graphs with a million nodes.

In backtracking the tree is implicit. A node is a partial solution (three letters of a five-letter word, four queens placed on an eight-by-eight board) and an edge is one more choice. Nothing builds that tree ahead of time. You generate children as you go and discard them as soon as you return. The full tree can be astronomically larger than anything you could store, which is why you must be willing to abandon branches early.

So the two extra steps are these. First, undo: when you return from a child, you restore the state to what it was before you made the choice. Second, prune: before descending, you check whether the partial solution can still lead anywhere, and you refuse to go if it cannot. A DFS with neither is a traversal. A DFS with both is backtracking.

What does the code look like side by side?

The code differs by a couple of lines, and those lines carry all the meaning. Here is a plain DFS on an adjacency list, followed by a permutation generator, which is the smallest honest backtracking example.

def dfs(node):
    seen.add(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(nxt)

def permute(path, used):
    if len(path) == n:
        out.append(path[:])
        return
    for i in range(n):
        if used[i]:
            continue
        used[i] = True
        path.append(nums[i])
        permute(path, used)
        path.pop()
        used[i] = False

Look at the seen set in the first function. It is written to and never cleared. In the second function, used[i] is set to True before the recursive call and set back to False after it, and path.pop() does the same for the path. That symmetric pair, choose and unchoose, is the signature of backtracking. If you cannot find it, you are probably looking at a traversal.

The second function also has no input graph. The "edges" are the loop over i, and the "nodes" are lists that exist only on the call stack for a moment. That is the implicit tree in action. If recursion itself still feels slippery, the idea of treating each call as an induction step, covered in recursion as induction, makes both functions easier to reason about.

Why does backtracking need an undo step?

Undo exists because in backtracking, state belongs to the route you are on, not to the place you are standing. Here is the framing I use. Imagine walking through a house and switching on the light in each room you enter. DFS leaves the lights on: once a room has been lit it counts as handled for the rest of the search, and no later route needs to enter it. Backtracking switches each light off as you walk back out, so every new route starts in a dark house and sees only its own rooms lit. The walk is the same. The lights are a record of the current route rather than a record of the whole search.

That distinction decides correctness. Take a word search on a grid, where you must decide whether a word can be spelled by stepping between adjacent cells without using any cell twice within a single spelling. Suppose you mark cells as visited and never unmark them. A failed attempt that started in the top-left corner leaves its cells blocked, and a later attempt that would have succeeded through a different route finds them closed. You will miss valid words, and the bug is silent: the code runs, returns false, and looks plausible. The mark must be undone because "used" means "used on this path".

Compare number of islands, where you count clumps of connected land. There "visited" means "already counted". Every route into that cell leads to the same clump, so the mark is permanent and no undo is needed. It is the same grid and the same four-direction loop, but the right answer to "do I unmark?" flips because the question being asked has changed.

The other half of undo is the early return. A common bug is a base case or pruning check that returns after the state was modified but before the unchoose line runs. The caller then sees a corrupted path, and every sibling branch inherits the damage. The habit that prevents this is to do all your checks before you modify anything, or to keep the choose and unchoose lines adjacent to the recursive call with nothing that can return in between.

How much more does backtracking cost than DFS?

Often exponentially more, and the reason is the missing visited set. A DFS visits each node once, so on a graph with 100,000 nodes and 400,000 edges it does roughly 500,000 units of work. Backtracking has no such cap, because the same element appears in many different partial solutions.

Work through permutations of 8 distinct items. The tree has 1 root, then 8 nodes at depth one, 56 at depth two, 336 at depth three, 1,680 at depth four, 6,720 at depth five, 20,160 at depth six, 40,320 at depth seven, and 40,320 leaves at depth eight. That sums to 109,601 nodes, which is about e times 8!. A few hundred thousand operations is nothing, so n = 8 feels harmless.

Now go to 12 items. There are 12! = 479,001,600 leaves, and the total node count is again about e times 12!, roughly 1.3 billion. At a hundred million nodes per second in a compiled language that is about 13 seconds. In CPython at a couple of million calls per second it is more than ten minutes. The code is identical. Only n moved from 8 to 12, and the cost grew by a factor of about 12,000.

This is why pruning is the real work. Consider eight queens. If you choose any 8 of the 64 squares, there are C(64, 8) = 4,426,165,368 placements. Restrict yourself to one queen per row and it falls to 8^8 = 16,777,216. Now reject a square the moment it shares a column or diagonal with an earlier queen, and the search tree has only about two thousand nodes and finds all 92 solutions. That is a factor of roughly eight thousand against the one-per-row version, and nothing about the traversal order changed. The cutoff did it.

I take two things from those numbers. Order does not make a search fast; a cutoff does. And a DFS bound like O(V + E) is a gift of the visited set, which backtracking has deliberately given up in exchange for the ability to explore every route.

There is a middle path. If the same partial state recurs through different routes, for example "index 5, remaining target 7" in a subset-sum search, you can cache the result by that state. The exponential tree collapses into a table of distinct states, and you have arrived at dynamic programming by a different door. The memoisation versus tabulation concept page covers that transition in detail.

How do DFS and backtracking compare side by side?

The table below puts the three variants next to each other, including the memoised form, since that is where the boundary with dynamic programming sits.

PropertyGraph DFSBacktrackingBacktracking with memo
Search spaceExplicit graph, grid or tree in memoryImplicit tree of partial solutionsImplicit tree, collapsed to distinct states
Meaning of a visited markHandled globally, permanentUsed on this path, temporaryResult cached per state, permanent
Undo on returnNoYes, restore state exactlyYes for path state, none for the cache
PruningRarely neededEssential for usable speedHelpful but less critical
Typical costO(V + E)Exponential or factorial in depthNumber of distinct states times work per state
Example, n = 8 and 12109,601-node graph: about 0.5M operations8! permutations: 109,601 nodes; 12!: about 1.3 billion nodesSubset sum with index and target: a few thousand states
Typical problemsConnected components, reachability, cycle detectionPermutations, subsets, N-Queens, sudoku, word searchSubset sum, partitioning, counting paths with a budget

The row I would stress is the second one. Everything else follows from what a visited mark means. If a mark means "I have dealt with this node for good", you are doing a traversal and the cost is bounded by the size of the graph. If it means "this is on my current route", you are doing a search, and the cost is bounded only by how many routes exist.

How do you decide which one a problem needs in an interview?

Ask whether the answer depends on the route taken or only on the place reached. If only the place matters, you want DFS. If the route matters, you want backtracking. Three questions make this concrete:

  1. Is the structure given to me, or do I generate it by making choices? Given structures lean towards DFS; generated ones lean towards backtracking.
  2. When I mark something visited, should a different route be allowed to use it again? If yes, you need to undo the mark.
  3. Can I reject a partial answer before it is complete? If you can, write the pruning check first, because it decides whether the solution finishes at all.

Wording in the problem statement is a good tell. Phrases like "is there a path", "how many components" and "can every node be reached" point to DFS. Phrases like "return all", "list every arrangement", "generate" and "place without conflict" point to backtracking. Output size is another tell: if the expected output can have millions of entries, nobody is expecting a linear-time solution, and the interviewer is looking at your pruning.

The boundary is blurry in one common case. Many tree problems, such as collecting every root-to-leaf path with a given sum, keep a shared path list and pop from it on return. That is the choose and unchoose pattern. But a tree has no cycles and each node is reached by exactly one route, so there is no visited set and the cost is still O(n) plus the cost of copying the paths out. I call this backtracking-style bookkeeping on a plain DFS. The diagnostic is whether the search space is bounded by the structure you were given. If it is, you are still in DFS territory in terms of cost, even though you borrowed the undo idiom. For the broader question of how to define what goes in the state, the state design template is a useful companion.

One more practical point. When you append a path to the results, append a copy, as in path[:] above. Appending the list itself stores a reference that the undo steps will empty before you finish, so every answer ends up blank. It is the single most common bug I see in first attempts at subsets and permutations, and it is worth checking before anything else when your output looks wrong but the count looks right.

If you want the traversal side of this comparison in more depth, the contrast with level-order search is laid out in when to use BFS vs DFS, and the underlying graph material lives under graphs.

Frequently asked questions

Is backtracking a type of DFS?

Yes, in the sense that backtracking explores its search tree depth first. What makes it backtracking rather than plain DFS is the undo of state on return and the pruning of branches that cannot succeed. Without those two parts you have a traversal.

Can backtracking be done with BFS or iteratively?

Iteratively, yes, using an explicit stack that records both the choice and the undo action. With BFS it stops being backtracking in practice, because each queue entry has to carry its own full copy of the state. For permutations of 8, the frontier at depth seven would hold 40,320 separate lists at once.

Why is DFS linear while backtracking is exponential?

DFS marks nodes permanently, so each of the V nodes and E edges is processed once. Backtracking clears its marks on the way back, so the same element can appear in an enormous number of different routes, giving counts like n! for permutations or 2^n for subsets. Pruning and memoisation are the two ways to claw that cost back.

For a concrete next step, solve Number of Islands with a permanent visited mark, then change the rule so a cell may be reused on a different route and watch which parts of your code must now undo themselves.