## Backtracking

**Pre-Requisite**: Depth-First Search

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.

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:

### 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:returnpath.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 stackif total > target:path.pop()returnif 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 pathif 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:returnpath.append(node.val)total += node.valif total > target:path.pop()returnif 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:returnpath.append(node.val)total += node.valif total > target:path.pop()returnif 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: 4path: [4]

def backtrack(node, path, total):if not node:returnpath.append(node.val)total += node.valif total > target:path.pop()returnif 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: 6path: [4,2]

def backtrack(node, path, total):if not node:returnpath.append(node.val)total += node.valif total > target:path.pop()returnif 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: 7path: [4,2,1]

def backtrack(node, path, total):if not node:returnpath.append(node.val)total += node.valif total > target:path.pop()returnif 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: 7path: [4,2,1]

**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:returnpath.append(node.val)total += node.valif total > target:path.pop()returnif 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:returnpath.append(node.val)total += node.valif total > target:path.pop()returnif 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: 4path: [4]

def backtrack(node, path, total):if not node:returnpath.append(node.val)total += node.valif total > target:path.pop()returnif 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: 6path: [4,2]

def backtrack(node, path, total):if not node:returnpath.append(node.val)total += node.valif total > target:path.pop()returnif 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: 6path: [4,2]

#### 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(n2), 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(n2).

**Space Complexity:** O(n2), 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.

Loading comments...