Backtracking

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.

word search backtracking

0 / 11

This example demonstrates key characteristics of backtracking algorithms:

It finds a solution 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 where all nodes have positive, integer values and a target sum, find all root-to-leaf paths where the sum of the values along the path equals the given sum.

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:

9 != 11. Next step: backtrack

0 / 5

Pay attention to step 2 / 4, in which we stop exploring the path before reaching the leaf node because the sum of the path exceeds the target sum. This is known as "pruning".

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.

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


def pathSum(root, target):
  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()
  
  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.


def pathSum(root, target):
  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()
  
  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 backtrack function is called once for each node in the tree. Each call takes O(n) time in the worst case to copy the path to the result list, resulting in a total time complexity of O(n²).

Space Complexity: O(n²), where n is the number of nodes in the binary tree. This is dominated by the size of the result list, which can contain up to O(n) paths, each of which can contain up to O(n) nodes.

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.

Next: Word Search

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

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Breadth-First Search: Bus Routes

Word Search

Backtracking

Pre-Requisite: Depth-First Search

word search backtracking

0 / 11

This example demonstrates key characteristics of backtracking algorithms:

It finds a solution 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 where all nodes have positive, integer values and a target sum, find all root-to-leaf paths where the sum of the values along the path equals the given sum.

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:

9 != 11. Next step: backtrack

0 / 5

Pay attention to step 2 / 4, in which we stop exploring the path before reaching the leaf node because the sum of the path exceeds the target sum. This is known as "pruning".

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.

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 3: The next function on the call stack then resumes and explores its right child (Node 5).


def pathSum(root, target):
  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()
  
  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.


def pathSum(root, target):
  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()
  
  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

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.

Next: Word Search

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

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103