Overview

Backtracking is a technique to recursively build a solution incrementally. You can think of it as a way to search through all possible solutions (almost akin to brute force with a few constraints).

There are two main categories of problems that backtracking solves:

1. Combinatorial Problems involve returning a combination or permutation of a given input. This is the most common case of backtracking.

   Example: Find all possible dice rolls to sum to a given target.

2. Validation Problems involve figuring out if a given statement is true or not. These questions are less common and can sometimes be tricky to notice that they involve backtracking.

   Example: Determine if it is possible to find a word in a word search grid.

Pattern concept

To demonstrate backtracking, let's start with a simple example: Get all subsets from a list of unique elements.

Step 1 of 32

Use ← → arrow keys

Solution template

# === Recursive Helper Function ===
def helper(self, i: int, curr: List[int], nums: List[int], res: List[List[int]]):
  # === Valid Result Check ===
  if i == len(nums):
    res.append(curr.copy())
    return
  
  # === Decision Tree ===
  curr.append(nums[i])  # To take...
  self.helper(i + 1, curr, nums, res)
  curr.pop()  # Or not to take...
  self.helper(i + 1, curr, nums, res)

# ==== Original function ====
def get_subsets(nums: List[int]):
  # === Result List Initialization ===
  res = [] 
  helper(0, [], nums, res)
  return res
  
print(get_subsets([5, 9, 7]))
    

There are two main steps to solve a backtracking question:

• Valid Result Check

  Make sure that the current possible combination is valid.

  A common example to do this is checking if we reached the end of the input list. A less common example is checking if a set of parenthesis are balanced.

  Note

  Be careful when adding the current list to the result list. Make sure to add a copy of the current list, otherwise you will end up modifying that list later in the algorithm.

• Decision Tree

  Backtracking brute forces finding all possible combinations. This is the part where we incrementally build a possible solution. It can include these decisions:

  • Take the element and recurse further into the branch.
  • Don't take the element (remove it if it was already added).
  • Try a different possible element by recursing into a different branch.

Besides the core code segments there are a few other auxiliary code segments to mention:

• Recursive Helper Function

  All backtracking questions require recursion. Not only that, all backtracking questions require a few necessary parameters:

  1. The current index that you are on
  2. The current solution you are building
  3. The input set
  4. The result list of all solutions (combinatorial problems) or a boolean result (validation problems)

• Result List Initialization (Combinatorial Problems Only)

  The code for this section will always be the same. Initialize an empty result list and pass it to your recursive function. This list will then be populated with the valid combinations once the backtracking process is done.

  Note

  If you're asked for combinations ([[1,2,3], [3, 2, 1]]), return the result list. If you're asked for number of combinations (2 combinations), return the result list's length.

How to identify

Does the problem involve any of these?

• Collecting a set of combinations / permutations / partitions of a given input
  • Get all subsets from a list of unique elements.
  • Letter Combinations of a Phone Number: Find all letter combinations of a given phone number.
  • Combination Sum: Find all unique combinations of numbers in a given list that sum up to a specific target.
  • N Queens: Generate all possibilities where you can place n queens on a chessboard in a way where no two queens threaten each other.
• A validation problem (true / false) involving the incremental building of a solution
  • Combination Sum (Variant): Check if you can add to a target number using n numbers.
  • Word Search: Determine whether a given word can be formed by connecting adjacent letters in a grid without revisiting a letter.