Limited Time Offer:Up to 20% off Hello Interview Premium

⌘K

Tutor

Backtracking

Backtracking Overview

Backtracking algorithms use Depth-First Search to search all possible paths for a solution to a path. The animation below shows how a backtracking algorithm finds the word "HELLO" using cells that are adjacent to each other in a 2D-grid.

The algorithm starts with "H" and explores all possible word paths by adding adjacent cells to the current word. As soon as the current word doesn't match "HELLO", the algorithm backtracks to the previous cell and tries the next path.

Visualization

word search backtracking

0 / 11

This example demonstrates key characteristics of backtracking algorithms:

It finds a solution for the problem by exploring all possible paths.
It "backtracks" to the previous path as soon as the current path doesn't lead to a solution.

Let's now look at an example of how to use Depth-First Search to solve backtracking problems.

Example: Path Sum

DESCRIPTION

Given a binary tree and a target sum, find all root-to-leaf paths where the sum of the values along the path equals the given sum. For this example, all nodes have positive integer values.

Example: Target: 7

Output:

[[4, 2, 1]]

This problem is a good backtracking candidate because it requires exploring all root-to-leaf paths to see if they sum to the given target.

The animation below visualizes the different paths the backtracking algorithm explores on the binary tree below with target = 11:

Visualization

path sum backtracking

0 / 34

Watch for the steps where we stop exploring a path before reaching a leaf node because the running total exceeds the target sum. This is known as "pruning" — it lets us skip entire subtrees we know can't lead to a valid solution.

Backtracking Solution

To implement this algorithm, we'll use depth-first search to explore all possible root-to-leaf paths.

We define a helper function backtrack that performs the depth-first search. backtrack takes the current node, the current path, and the current sum as arguments.

Each recursive call of backtrack explores the current node by adding the node's value to the path and incrementing the total sum.

If the current node is a leaf node, we check if the total sum equals the target sum. If it does, we add the path to the result list. We then backtrack to the previous node in the tree.

Otherwise, it makes recursive calls to explore the left and right children of the current node.

Solution

def pathSum(root, target):
    def backtrack(node, path, total):
        if not node:
            return
        
        path.append(node.val)
        total += node.val
        # KEY STEP 2
        # current sum exceeds target
        # so pop to remove the current node from the path
        # return to backtrack to previous node on the call stack
        if total > target:
            path.pop()
            return
        
        if not node.left and not node.right:
            # add the path to the result
            # note we have to make a copy (path[:]) of the path
            # since future recursive calls modify path
            if total == target:
                result.append(path[:])
        else:
            backtrack(node.left, path, total)
            backtrack(node.right, path, total)
        # KEY STEP 1
        # we have finished exploring all paths containing the current node
        # so pop to remove the current node from the path
        # return to backtrack to previous node on the call stack.
        path.pop()
    result = [] 
    backtrack(root, [], 0)
    return result

Key Steps

The key to understanding backtracking algorithms is to understand what happens when a recursive call returns.

KEY STEP 1: Backtracking

The animation below shows how the algorithm "backtracks" after processing the first leaf node (Node 2 at the bottom left of the tree).

Step 1: The function first adds the value of the leaf node to the path and increments the total of the path.

Step 2: Since we're at a leaf node, the function checks if the current sum equals the target sum. It doesn't here, the function first pops the leaf node from the path list before the function call returns and backtracks to the previous node in the tree.

Step 3: The next function on the call stack then resumes and explores its right child (Node 5).

Visualization


def pathSum(root, target):
    result = []
    backtrack(root, [], 0)
    return result


def backtrack(node, path, total):
    if not node:
        return
        
    path.append(node.val)
    total += node.val
    if total > target:
        path.pop()
        return
    if not node.left and not node.right:
        if total == target:
            result.append(path[:])
    else:
        backtrack(node.left, path, total)
        backtrack(node.right, path, total)
    path.pop()

total: 4
path: [4]


def backtrack(node, path, total):
    if not node:
        return
        
    path.append(node.val)
    total += node.val
    if total > target:
        path.pop()
        return
    if not node.left and not node.right:
        if total == target:
            result.append(path[:])
    else:
        backtrack(node.left, path, total)
        backtrack(node.right, path, total)
    path.pop()

total: 6
path: [4,2]


def backtrack(node, path, total):
    if not node:
        return
        
    path.append(node.val)
    total += node.val
    if total > target:
        path.pop()
        return
    if not node.left and not node.right:
        if total == target:
            result.append(path[:])
    else:
        backtrack(node.left, path, total)
        backtrack(node.right, path, total)
    path.pop()

total: 7
path: [4,2,1]


def backtrack(node, path, total):
    if not node:
        return
        
    path.append(node.val)
    total += node.val
    if total > target:
        path.pop()
        return
    if not node.left and not node.right:
        if total == target:
            result.append(path[:])
    else:
        backtrack(node.left, path, total)
        backtrack(node.right, path, total)
    path.pop()

total: 7
path: [4,2,1]

recursive call

0 / 3

Key Step 2: Pruning

The animation below shows how the algorithm "prunes" paths when the current sum exceeds the target sum at Node 8.

Step 1: The function first adds the value of the current node to the path and increments the total of the path.

Step 2: The function checks if the current sum exceeds the target sum. It does here, so the function immediately pops the current node from the path list before the function call returns and backtracks to the previous node in the tree.

Step 3: The next function on the call stack then resumes (Node 2). Since all paths containing Node 2 have been explored, the function pops Node 2 from the path and backtracks to the previous node in the tree.

Visualization


def pathSum(root, target):
    result = []
    backtrack(root, [], 0)
    return result


def backtrack(node, path, total):
    if not node:
        return
        
    path.append(node.val)
    total += node.val
    if total > target:
        path.pop()
        return
    if not node.left and not node.right:
        if total == target:
            result.append(path[:])
    else:
        backtrack(node.left, path, total)
        backtrack(node.right, path, total)
    path.pop()

total: 4
path: [4]


def backtrack(node, path, total):
    if not node:
        return
        
    path.append(node.val)
    total += node.val
    if total > target:
        path.pop()
        return
    if not node.left and not node.right:
        if total == target:
            result.append(path[:])
    else:
        backtrack(node.left, path, total)
        backtrack(node.right, path, total)
    path.pop()

total: 6
path: [4,2]


def backtrack(node, path, total):
    if not node:
        return
        
    path.append(node.val)
    total += node.val
    if total > target:
        path.pop()
        return
    if not node.left and not node.right:
        if total == target:
            result.append(path[:])
    else:
        backtrack(node.left, path, total)
        backtrack(node.right, path, total)
    path.pop()

total: 6
path: [4,2]

recursive call

0 / 3

Key Takeaways

Returning from a function corresponds to backtracking to the previous node in the tree.
Since we use a single list to store the current path across all recursive calls, before returning, we have to pop the current node from that path to backtrack.

Time and Space Complexity

Time Complexity: O(n²), where n is the number of nodes in the binary tree. The DFS visits each node once. Path copying only happens at leaf nodes — each copy takes O(h) time where h is the depth of that leaf. The total cost of all path copies is the sum of all root-to-leaf path lengths, which is O(n²) in the worst case (a skewed tree with leaves at varying depths). For a balanced tree, this reduces to O(n log n) since every leaf sits at depth O(log n).

Space Complexity: O(n²), where n is the number of nodes in the binary tree. This is dominated by the result list, which can hold up to O(n) paths each up to O(n) nodes long. The recursion stack adds O(h) space where h is the height of the tree.

Summary

The above algorithm is a good example of a backtracking algorithm because:

It explores all possible root-to-leaf paths in the binary tree to find the paths that sum to the target sum.
Whenever we reach a leaf node, we backtrack to the previous node in the tree to explore the next path.
It "prunes" paths by returning immediately when the sum exceeds the target sum.

Mark as read

Next: Word Search

Your account is free and you can post anonymously if you choose.

Unlock Premium Coding Content

Interactive algorithm visualizations

Guided Practice

Recent interview questions

Learn More

Reading Progress

On This Page

Example: Path Sum

Backtracking Solution

Key Steps

Summary

Backtracking

Backtracking Overview

Example: Path Sum

DESCRIPTION

Backtracking Solution

Key Steps

Key Takeaways

Time and Space Complexity

Summary

Comments

Questions

Learn

Links

Legal

Contact