DFS vs Backtracking: One Has a Visited Set, the Other Has an Undo Step

You see a recursive function that goes deep before going wide. It looks like DFS. The interviewer says "DFS." The candidate says "backtracking." Neither pushes back. Both move on. Everyone is mildly confused.

They look nearly identical in code. Both use recursion. Both explore branches before returning. The terminology gets used interchangeably in problem discussions, and most candidates let it slide because correcting the interviewer feels risky.

The real distinction: DFS marks nodes visited and never undoes that mark. Backtracking marks state, explores, then explicitly undoes the mark before trying the next choice.

Everything else follows from that one sentence.

DFS Is About Traversal

DFS answers one question: what nodes can I reach from a starting point?

The graph already exists. The nodes are there, the edges are there. You pick a start node, recurse into unvisited neighbors, mark each one as visited so you don't revisit it, and keep going until you run out of unvisited neighbors.

def dfs(graph: dict, node: int, visited: set) -> None:
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Notice what never happens here: visited nodes stay visited. Once you mark a node, you never unmark it. The traversal moves forward, the visited set grows, and the function exits when there's nothing left to visit.

Both are intentional. For graph DFS, you want visited to be permanent. Without it, any cycle turns your recursion into an infinite loop. The visited set is the whole reason DFS terminates on graphs.

DFS complexity is O(V+E): each vertex visited once, each edge traversed at most twice. Space is O(V) for the visited set plus O(V) stack depth in the worst case (a path graph with no branching).

An undirected graph with six numbered nodes. DFS traversal arrows show the order of visitation. Every node has a permanent checkmark. No marks are ever removed.

DFS: the visited set is a one-way ratchet. It only grows.

Typical DFS problems: count connected components (LeetCode 200), detect cycles, topological sort, check if a path exists between two nodes. See the depth-first search algorithm explainer for the full template and all five DFS patterns.

Backtracking Is About Building Solutions

Now flip the question. Instead of "what can I reach?", ask "what complete solutions can I build?"

You're not traversing a graph that already exists. You're exploring a decision tree you construct on the fly. Each node in this tree represents a partial solution. Each edge represents a choice you haven't committed to yet. The tree doesn't exist until you create it by recursing.

The critical requirement: when you finish exploring one subtree, you must undo your choices so the next subtree starts from a clean state.

def backtrack(path: list, remaining: list, result: list) -> None:
    if not remaining:
        result.append(path[:])   # copy the current solution
        return
    for i, choice in enumerate(remaining):
        path.append(choice)                              # choose
        backtrack(path, remaining[:i] + remaining[i+1:], result)  # explore
        path.pop()                                       # unchoose

That path.pop() at the end is the whole game. Without it, the next branch inherits a corrupted path from the previous branch, and your results are silently wrong. Not wrong with an error. Not wrong with a traceback. Silently, mysteriously, impressively wrong in a way that's annoying to debug at 2am.

Backtracking complexity is typically O(b^d), where b is the branching factor and d is the depth of the decision tree. For permutations of n elements, the tree has n! leaves, and each leaf costs O(n) to copy, giving O(n * n!). For subsets, the tree has 2^n leaves at O(n) copy cost each, giving O(n * 2^n). See backtracking time complexity for the full derivations.

A decision tree for all permutations of [1, 2, 3]. Blue arrows descend on each "choose". Amber dashed arrows rise on each "path.pop()". Every down-arrow has a matching up-arrow. Leaves are the six complete permutations.

Every choose has a matching unchoose. The amber arrows are path.pop() firing as the recursion unwinds.

The Undo Step Is the Whole Difference

Here's the comparison in one table. One column has a permanent mark, the other doesn't:

	DFS	Backtracking
Purpose	Traverse an existing graph	Enumerate valid solutions
Search space	Explicit graph (V and E given)	Implicit decision tree
State after returning	Visited nodes stay visited	Choices are undone
Pruning	Visited check only	Any constraint predicate
Typical complexity	O(V+E)	O(b^d)
Space	O(V)	O(d) stack + output

The visited set in DFS is a permanent record. The path in backtracking is a temporary scratchpad. One grows monotonically. The other shrinks back on every return.

That's it. That's the whole distinction. Everything else is downstream of whether you undo your state.

When the Same Problem Uses Both

Some problems need the DFS movement pattern but require the backtracking undo step. This is where candidates get into trouble, because the code looks like DFS but you're actually doing backtracking.

LeetCode 79, Word Search. You have a 2D grid of characters and a target word. You need to find if you can spell the word by moving up/down/left/right through the grid, using each cell at most once per path.

Your first instinct: use DFS with a global visited set. That's wrong. A cell that's been visited on one path isn't globally off-limits. It's just unavailable for the current path. A different path is perfectly allowed to use it.

So you use the backtracking trick: mark the cell before recursing, unmark it on return.

def backtrack(grid: list, word: str, i: int, j: int, k: int) -> bool:
    if k == len(word):
        return True
    if (i < 0 or i >= len(grid) or
        j < 0 or j >= len(grid[0]) or
        grid[i][j] != word[k]):
        return False

    tmp = grid[i][j]
    grid[i][j] = '#'      # mark: this cell is on the current path

    found = (backtrack(grid, word, i+1, j, k+1) or
             backtrack(grid, word, i-1, j, k+1) or
             backtrack(grid, word, i,   j+1, k+1) or
             backtrack(grid, word, i,   j-1, k+1))

    grid[i][j] = tmp      # unmark: path unwinds, cell is available again
    return found

The mark is path-scoped, not global. That's what makes it backtracking rather than DFS.

Now compare to Number of Islands (LeetCode 200). There, you mark cells permanently. Once a cell belongs to an island, it's done. You never need to unmark. Pure DFS.

Same grid. Same recursive structure. Different lifecycle of the mark. That single difference determines which algorithm you're running.

Two 4x4 grids side by side. Left: DFS for Number of Islands, cells marked with permanent checkmarks, no restoration arrows. Right: Backtracking for Word Search, one cell marked '#' on recursion in, then restored to its original letter on return. Same grid structure, completely different mark lifecycles.

Left: permanent. Right: temporary. The grids look identical. The algorithms are not.

Three Questions to Figure Out Which You Need

When you see a recursive search problem, ask these in order. This takes about ten seconds and saves you from implementing the wrong thing.

1. Does an explicit graph exist, or are you building the search space as you go?

Pre-existing nodes and edges mean DFS. You're just traversing. If the "nodes" are partial solutions that don't exist until you construct them, you're doing backtracking.

2. Do you need to undo any state when returning from a recursive call?

If anything you modify must be restored on return, it's backtracking. If the modification can stay permanent for the rest of the search, it's DFS.

3. Are you enumerating all solutions, or checking reachability?

Reachability, connectivity, counting components: DFS. Finding all valid solutions, constraint satisfaction, generating all permutations/subsets/combinations: backtracking.

The edge case that trips people: finding all paths from source to destination in a graph. The movement is DFS. But because you must unmark nodes as you return (a node can appear on multiple distinct paths), it's backtracking on an explicit graph. They can coexist.

The Spectrum: Four Levels of Search

There's a natural progression of sophistication. Each stage adds exactly one concept on top of the previous:

Pure DFS explores everything, no visited set, no undo. Use for trees (no cycles, so no revisiting needed). Every node visited exactly once by the tree structure alone.

DFS with a visited set prevents revisiting nodes in graphs. State changes are permanent. Use for connectivity, cycle detection, topological sort.

Backtracking adds the undo step plus feasibility pruning. You abandon a branch the moment it violates a constraint, before recursing further. Use for constraint satisfaction and enumeration.

Branch and Bound adds optimality pruning on top of backtracking. You abandon branches that can't improve on the best solution found so far. Use for optimization problems like TSP and 0-1 knapsack. Rarely shows up in coding interviews. Mostly shows up in algorithm textbooks you read at 1am before a hard interview.

A horizontal spectrum bar with four sections: Pure DFS (trees), DFS + Visited Set (graphs/cycles), Backtracking (constraints/enumerate), Branch and Bound (optimize). Each stage is annotated with a +1 showing the concept it adds.

Interviews mostly live in the middle two. Branch and Bound is the final boss nobody asks about.

Pruning: The Only Way to Tame O(b^d)

Backtracking's exponential worst case sounds terrifying. It is, in theory. In practice, pruning is what keeps it runnable, and this is where the craft actually lives.

Feasibility pruning abandons a branch the moment it violates a constraint, before recursing into it. In N-Queens, if placing a queen on row k conflicts with any existing queen on the board, you skip to the next column immediately. You never recurse into a subtree that's already dead. This is what keeps N-Queens practically solvable for n up to around 15.

Optimality pruning (the Branch and Bound variety) abandons a branch when its best possible outcome can't beat the current best solution. Only needed for optimization problems, not for pure enumeration.

The tighter your pruning predicate, the smaller the actual search space. A perfectly pruned backtracking search can collapse to polynomial time on structured inputs, even though the theoretical bound is exponential. The theoretical bound describes a problem with no structure. Real problems always have structure.

An N-Queens decision tree for n=4. Root tries columns 0-3. From the (0,0) branch, columns 0 and 1 in row 1 are crossed out immediately on conflict check before any recursion occurs. Only column 2 survives. Caption: the conflict check fires before the recursive call.

The red X fires before the recursive call. That's what makes it pruning, not just early returning.

Complexity at a Glance

Problem	Algorithm	Time	Space
Count islands	DFS	O(m * n)	O(m * n)
Has path A to B	DFS	O(V+E)	O(V)
All paths A to B in graph	Backtracking	O(V!) worst	O(V)
All subsets of n elements	Backtracking	O(n * 2^n)	O(n)
All permutations of n	Backtracking	O(n * n!)	O(n)
Word search, word length L	Backtracking	O(m * n * 4^L)	O(L)
N-Queens	Backtracking (pruned)	O(n!)	O(n)
Topological sort	DFS	O(V+E)	O(V)
Detect cycle	DFS	O(V+E)	O(V)

The Word Search bound of O(m * n * 4^L) is loose: the character matching prunes aggressively in practice, and you rarely explore all 4^L paths from any starting cell.

The Recap

DFS is a traversal algorithm. Backtracking is a problem-solving strategy that uses DFS as its movement engine.
The defining feature of backtracking is the undo step. Every choose must have a matching unchoose when the recursion returns.
DFS visited state is permanent. Backtracking state is path-scoped and temporary.
DFS traverses an explicit graph. Backtracking explores an implicit decision tree it builds during the search.
Word Search is backtracking disguised as DFS: the mark is path-scoped. Number of Islands is pure DFS: the mark is global.
Pruning is what keeps backtracking tractable. Abandon branches early on constraint violations.
The progression is: DFS then DFS+visited then Backtracking then Branch and Bound. Each stage adds one concept.

For a deeper look at the backtracking template and every pruning category, see the backtracking algorithm deep dive.

If you want to practice explaining the difference out loud under interview conditions, SpaceComplexity runs voice-based DSA mock interviews with rubric-scored feedback. Knowing that you need backtracking is half the score. Explaining why the undo step is required is the other half.