DFS vs Backtracking — The Distinction That Trips Most Candidates

Backtracking is DFS, technically. But the interview vocabulary distinguishes them — and picking the wrong word (or worse, writing DFS when the problem needs backtracking) is a real interview tell. This post is the tie-breaker: what each preserves, when the choose/undo rhythm earns its keep, and why the distinction matters even though both are recursion over a search space.

The verdict

DFS visits every reachable node in a graph or tree exactly once. State is either global (a visited set) or immutable per call. The goal is usually "explore everything" — count components, find a path, check reachability.

Backtracking explores a decision tree by making a choice, recursing, and undoing the choice before trying the next sibling. State is mutable and path-specific — every branch of the tree gets a clean slate. The goal is usually "enumerate all valid solutions" — subsets, permutations, valid placements.

Same shape (recursion), same worst-case time on unpruned inputs. The distinction is whether the state you carry differs between siblings. If yes, you need choose/undo — that's backtracking. If no, plain DFS is enough.

When to reach for DFS

• Exploring a graph or tree once. Reachability, component sizes, tree shapes. The visited set makes sure you don't revisit anything.
• The state is immutable or shared globally. Depth, ancestors, running max — pass as function arguments or maintain in a class field. Nothing needs undoing.
• You want any path or any solution, not all of them. Return early on the first hit.
• Traversal-flavoured problems. LC 200 (Number of Islands), LC 104 (Max Depth), LC 236 (LCA), LC 133 (Clone Graph). Each visits every reachable node once.

Cross-reference the BFS vs DFS post.

When to reach for backtracking

• Enumerating all valid configurations. Every combination of some choice.
• The state you carry is mutable and path-specific. current list of chosen elements, used array of taken items, board under construction.
• Constraints prune whole subtrees. N-Queens's column-and-diagonal check; sudoku's row/column/box check.
• The problem's answer is a list of solutions, not "did we find one?". LC 78 (Subsets), LC 46 (Permutations), LC 39 (Combination Sum), LC 51 (N-Queens).

Cross-reference the backtracking template post.

Side by side

Same shape, different behaviour

Consider the shared recursive skeleton:

def explore(state):
    if is_solution(state):
        record(state)
        return
    for choice in choices(state):
        # DFS: no mutation of state across siblings
        # Backtracking: MUTATE state before recursing, then UNDO
        explore(next_state(state, choice))

DFS. next_state returns a fresh state (or state is immutable — a node reference, an index). No cleanup after the recursive call because siblings never see each other's mutations.

Backtracking. state is a shared mutable object. Before the recursion, mutate it to reflect the choice. After, undo. Miss the undo and sibling branches inherit the wrong state — quietly wrong output.

Worked comparison — DFS (LC 200 Number of Islands)

Count connected components on a grid.

Visit every land cell once. Mark visited by overwriting '1' → '0' (a global mutation, not a per-path one — a cell that's been visited stays visited across every sibling call).

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    def dfs(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c); count += 1
    return count

No undo. Once we mark a cell visited, we mean it forever — no other branch of the search should reconsider it.

Worked comparison — backtracking (LC 78 Subsets)

Enumerate every subset of a distinct-element array.

Every branch of the decision tree carries its own current list. Choose an element, recurse; undo the choice; try the next sibling.

def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])          # snapshot every node — subsets include the empty set
        for i in range(start, len(nums)):
            current.append(nums[i])        # CHOOSE
            backtrack(i + 1, current)
            current.pop()                  # UNDO
    backtrack(0, [])
    return result

The current.append / current.pop mirror is what makes this backtracking. Without the pop, subsequent siblings inherit the append and produce nonsense output.

The rule of thumb

Ask: would leaving state modified after the recursive call corrupt sibling recursions?

• No — plain DFS. State is either immutable or its mutation should stick (like the visited set).
• Yes — backtracking. Mirror every mutation with an undo before the next sibling.

Same recursion skeleton. Same asymptotic bounds. The vocabulary distinction reflects a real invariant — and getting it right lets you (a) write correct code without hand-wringing, and (b) communicate clearly with interviewers who use the distinction as shorthand for what technique they expect.

Cross-references

• The BFS vs DFS post settles the first question — should this be DFS or BFS at all? If DFS, this post decides the sub-flavour.
• The backtracking template post is the canonical treatment of the choose/undo rhythm across subsets, permutations, and N-Queens.
• For the O(V + E) claim DFS cashes in on, and the exponential O(n · 2ⁿ) / O(n · n!) claims backtracking inherits, see the Big-O cheat sheet.