Backtracking

Backtracking explores choices recursively, undoing decisions when they lead nowhere.

Types of Backtracking Problems

Backtracking solves four main problem types: feasibility, enumeration, counting, and optimization. Using the subset sum problem (arr = [5, 1, -2, 7, -14, -2]) as an example:

All four variations share the same decision tree and are solved by DFS. For subsets, we simply decide for each element: pick it or not.

Decision Tree Modeling

Backtracking can be broken down into two steps:

1. Model the problem as a decision tree.
2. Implement a DFS through the decision tree.

It has little to do with coding—it's only about modeling how to get to the solution (or all solutions) as a sequence of decisions. We haven't shown any code yet because if we can first get a clear picture of the decision tree, the implementation part will feel a lot more intuitive.

If you can clearly visualize the decision tree, implementing backtracking will become a lot easier. We recommend drawing it out when possible, on paper if necessary.

• Jumping Numbers: A jumping number is a positive integer where every two consecutive digits differ by one (e.g., 2343). We can design a decision tree to find all jumping numbers smaller than some value n. We start with 0 digits and, at each step, we add one more digit.

• Balanced Parentheses: We can design a decision tree to find all balanced parentheses strings of some length. We start with an empty string and, at each step, we decide whether to add '(' or ')'.

  • Pruning: We can avoid partial strings that are already unbalanced. For instance, any string starting with ()) cannot be 'fixed' later, so we don't need to visit it nor extend it into longer strings. This is called pruning. The more we prune, the smaller the decision tree, making the backtracking DFS faster.

• Traveling Salesperson Problem (TSP): We can model this as a decision problem: we pick an arbitrary city as a starting point, then we build a path step by step by choosing where to go next among the remaining unvisited cities.

  Drawing Advice

  Even candidates who know how backtracking works still get stuck figuring out the implementation. We advise taking the time to draw the decision tree before implementing anything.

  Our advice for drawing decision trees is similar to the drawing advice for Trees. However, in backtracking questions, the tree may be huge. We recommend using either a tiny input or drawing just enough to give you a sense of the tree structure.

  Decision Tree Modeling Problem Set

  Model each of the following problems as finding a leaf or set of leaves in a decision tree. Think about the sequence of decisions that you need to make and whether you can prune any of them. We recommend drawing the decision tree for each problem. Do not code anything yet.

  Question 1 N-Queens Puzzle

  In Problem 28.1: Chess Moves, we described the movement of a queen in chess. Find all the ways to place n queens on an nxn board without any two of them being in the same row, column, or diagonal.
  Solution 1 N-Queens Puzzle

  There are a few ways we could model this puzzle as a decision tree. One *PROPERTY* we can use is that, to have n queens on an nxn board, each row must have exactly one queen. We can start with an empty grid. Then, we decide where to put a queen in the first row. At each step, we decide where to put a queen in the next empty row. We can **prune** columns and diagonals that already have a queen.
  Question 2 K-Combination Sum

  Given an array of unique integers, arr, and a positive number k, find whether there is any subset of arr of size k that adds up to 0.
  Solution 2 K-Combination Sum

  This would be like the decision tree for Subset Sum, except we stop at nodes that already picked k elements.
  Question 3 Graph Coloring

  Given an undirected, connected graph, and a positive number k, find whether it is possible to assign a color to each node, using only k different colors, in such a way that adjacent nodes always have different colors (there is no limit for how many nodes can have the same color, as long as they are not adjacent).
  Solution 3 Graph Coloring

  At the beginning, every node is uncolored. Then, we need to make a decision for each node: which of the k colors to assign to it. When choosing colors for a node, we can **prune** the colors of any neighbor that has already been colored.
  Question 4 4-Directional Max-Sum Path

  Given an RxC grid with positive and negative integers, find the path from the top-left cell to the bottom-right cell that maximizes the sum. You can go in all four directions (diagonals not allowed), but you **can't visit a cell more than once**.
  Solution 4 4-Directional Max-Sum Path

  This would be like the decision tree for the Max-Sum Path problem except that we would have extra children to also go up and left. We would also have to avoid revisiting cells already in the path, which means we could end at a dead end surrounded by already-visited cells. We should **prune** such branches.

  Implementation

  Backtracking is essentially a DFS on a conceptual decision tree, implemented via recursion. Unlike traversing a stored tree, we dynamically generate branches (choices) and carry the partial solution state through the recursive calls.

  Max-Sum Path Solution

  While Dynamic Programming is the optimal approach for this problem, we use Backtracking here to illustrate the concept of performing a DFS on a decision tree.

  python

  Copy

  def max_sum_path(grid): # Inefficient backtracking solution. DP is better!
      max_sum = -math.inf
      R, C = len(grid), len(grid[0])
      
      def visit(r, c, cur_sum):
          nonlocal max_sum
          if r == R - 1 and c == C - 1:
              max_sum = max(max_sum, cur_sum)
              return
          
          if r + 1 < R:
              visit(r + 1, c, cur_sum + grid[r + 1][c]) # Go down
          if c + 1 < C:
              visit(r, c + 1, cur_sum + grid[r][c + 1]) # Go right
              
      visit(0, 0, grid[0][0])
      return max_sum
  

  Each visit() call receives the current endpoint (r, c) and the accumulated sum.

  • Root: (0, 0) with cur_sum = grid[0][0].
  • Children: Obtained by increasing r or c (within bounds).
  • Leaf: Reached when (r, c) is (R - 1, C - 1).

  Note: Backtracking solutions can often be optimized with DP. Unlike traditional grid DFS (which avoids revisiting cells), backtracking may revisit the same cell via different paths.

  We can capture a generic decision tree DFS in a recipe:

  Recipe 1. Backtracking

  python

  Copy

  def visit(state):
      if is_complete(state):
          output(state)
          return
          
      for choice in get_choices(state):
          if not is_valid(state, choice):
              continue
          apply_choice(state, choice)
          visit(state)
          undo_choice(state, choice)
          
  visit(empty_state)
  

  How is this different from a traditional tree DFS?

  Binary Tree DFS	Backtracking DFS
  The binary tree is given to us as an explicit input.	We need to model the problem as a decision tree ourselves.
  The size of the input corresponds to the number of nodes in the tree.	The input format could be almost anything.
  The time and space analysis is typically measured in terms of the number of nodes in the input, which we call n.	The size of the tree is typically exponential on the size of the input.
  	The time can be analyzed with the BAD method (pg 401).

  Design Choices

  For each problem, we'll need to fill in concrete details in Recipe 1 and make some implementation choices:

  1. Solution state: What data structures do we need to represent partial solutions?
  2. Child creation: When we create a child, should we make new data structures for its state or modify the parent's state in place? As a rule of thumb, we'll modify data structures with non-constant-size like arrays or grids, as modifying is cheaper than creating new ones.
  3. Pruning: Should we prune eagerly (when generating the children) or lazily (as a base case in visit())? In particular, do we check boundary conditions before recursing or after?
  4. Leaf processing: What should we do with full solutions?
  5. Additional work optimization: Can we improve the runtime per node (or per leaf) by passing any extra information down the call tree?

  'Leaf processing' is the part that depends on the problem type. First, it involves checking if the full solution is valid. If it is, what we do with it differs:

  • Feasibility: save it so we can return it at the end.
  • Enumeration: appending the full solution to a 'global' array.
  • Counting: incrementing a 'global' counter.
  • Optimization: updating a 'global' variable tracking the best solution so far, if it's better.

  We don't need a different recipe for each problem type!

  Let's see the decisions we made for the Max-Sum Path problem:

  1. Solution state: for each partial solution, we only need the end of the partial path and the accumulated sum. Since we are just looking for the value of the solution and not the solution itself, we didn't need the entire partial path, so we don't bother passing it down the tree.
  2. Child creation: since the data structures consist of just three integers, it is straightforward to create new integers. Modifying the data structures in place makes sense only when they are more complicated.
  3. Pruning: we eagerly check if the children are out of bounds.
  4. Leaf processing: all full solutions end at the bottom-right corner, so we don't need a validity check. Since this is an optimization problem, we update a 'global' variable with the best value seen so far.
  5. Additional work optimization: we already spend O(1) time at each node, so there is no possible optimization here.

  Subsets & Permutations

  Most backtracking problems are variations of two core patterns: generating subsets or permutations.

  Pattern	Core Decision	Examples
  Subsets	Pick vs. Don't Pick: For each element, decide whether to include it in the subset.	Subset Sum, Valid Parentheses
  Permutations	Ordering: For each position, decide which remaining element to place next.	N-Queens, TSP

  Problem 1: Subset Enumeration

  Problem Generate All Subsets

  Given a set of elements S, return all possible subsets.

  • Example: S = ['x', 'y', 'z']
  • Output: [[], ['x'], ['y'], ['z'], ['x', 'y'], ['x', 'z'], ['y', 'z'], ['x', 'y', 'z']]
  Solution Subset Enumeration

  Each subset is created by making a decision for each input element: pick it or skip it.

  python

  Copy

  def all_subsets(S):
      res = [] # Global list of subsets.
      subset = [] # State of the current partial solution.
      def visit(i):
          if i == len(S):
              res.append(subset.copy())
              return
          # Choice 1: pick S[i].
          subset.append(S[i])
          visit(i + 1)
          subset.pop() # Cleanup work: undo choice 1.
          # Choice 2: skip S[i].
          visit(i + 1)
      visit(0)
      return res
  

  Unlike in the recipe, we don't need a loop for choices because there are only 2.

  • Solution state: subset is the current subset at each node.
  • Child creation: We share the subset array by modifying it in place. This requires cleanup work (popping S[i] after recursing).
  • Pruning: No pruning; we must visit both children to find all subsets.

  Reusable Idea: Modify -> Recurse -> Undo

  When you make a mess, clean it up. If you modify a shared variable before a recursive call, you must reverse that change immediately after the call returns.

  Problem 2: Permutation Enumeration

  Problem Generate All Permutations

  Given an array of unique characters, return all possible permutations.

  • Example: arr = ['x', 'y', 'z']
  • Output: [['x', 'y', 'z'], ['x', 'z', 'y'], ...] (all 6 orderings)
  Solution Permutation Enumeration

  At each step i, we decide which of the remaining elements (from index i onwards) to place at position i. We can do this by swapping elements into position i.

  python

  Copy

  def generate_permutations(arr):
      res = []
      perm = arr.copy()
      def visit(i):
          if i == len(perm) - 1:
              res.append(perm.copy())
              return
          for j in range(i, len(perm)):
              perm[i], perm[j] = perm[j], perm[i] # Pick perm[j] as the next element
              visit(i + 1)
              perm[i], perm[j] = perm[j], perm[i] # Cleanup work: undo change
      visit(0)
      return res
  

  • Base case: len(arr) - 1 because the last element has no other choice.
  • Swapping trick: We use the array itself to track picked vs. remaining elements. Indices 0 to i-1 are fixed; i to n-1 are available candidates.

  Analysis

  Decision Tree Size

  The runtime of backtracking is dominated by the size of the decision tree.

  • Depth: Typically linear on input size.
  • Branching Factor: Usually $ge 2$.
  • Total Nodes: $O(b^d)$, which is exponential. Backtracking is slow because it often traverses most of these nodes.

  The BAD Method

  We can bound the runtime using: $O(b^d imes A)$ Where:

  • $b$: Max branching factor
  • $d$: Max depth
  • $A$: Additional work per node (excluding recursion)

  Problem	Branching ($b$)	Depth ($d$)	Work ($A$)	Upper Bound
  Subsets	2 (pick/skip)	$n$	$O(n)$ (copy at leaf)	$O(2^n cdot n)$
  Permutations	$n$ (at root)	$n$	$O(n)$ (copy at leaf)	$O(n! cdot n)$

  Note: For permutations, $O(n^n)$ is a loose upper bound; $O(n!)$ is tighter and more accurate.

  Space Analysis

  • Enumeration Problems: Output size is exponential ($O(2^n cdot n)$ or $O(n! cdot n)$), which becomes the bottleneck.
  • Other Types: Space is $O(d imes S)$, where $d$ is recursion depth and $S$ is space per stack frame. If we modify state in-place, $S$ is constant. If we copy, $S$ is linear.

  Optimizing Backtracking

  Since the decision tree is exponential, we can't make it polynomial, but we can reduce its size:

  1. Modeling (Better Decision Tree):

     • Example (8-Queens):
       • Naive: Pick any square? $2^{64}$ leaves.
       • Better: One queen per row? $8^8 approx 16M$ leaves.
       • Best: Permutation of rows? $8! approx 40k$ leaves.

  2. Pruning:

     • Proactively remove nodes that can't lead to valid solutions.
     • Example (8-Queens): Don't place a queen if attacked by previous ones.
     • Impact: Doesn't change worst-case complexity class (still exponential), but dramatically improves practical runtime (like pruning an oak tree into a bonsai).

  Summary: Focus on minimizing the tree size ($b$ and $d$) first. Optimizing work per node ($A$) is secondary.

  Problem Set

  Question 1 To Be or Not To Be LeetCode 78

  Similar to LeetCode 78. Subsets

  Inspired by Shakespeare's iconic line, you decide to write a function, shakespearify(), which takes in a string, sentence, consisting of lowercase letters and spaces. For each word in the string, the function chooses if it should "be" or "not be" included in the sentence, returning all possible outcomes. The order of the output strings does not matter.

  • Example: sentence = "I love dogs"
  • Output: ["", "I", "love", "dogs", "I love", "I dogs", "love dogs", "I love dogs"]
  Solution 1 To Be or Not To Be

  This problem is a variant of the Subset Enumeration problem. Instead of focusing on individual characters, we must pick or skip entire words. The simplest way is to split the string into words in a preprocessing step before doing the recursive DFS. The picked words can be joined again into a string at the leaves.

  python

  Copy

  def shakespearify(sentence):
      words = sentence.split()
      res = []
      subset = []
      def visit(i):
          if i == len(words):
              res.append(" ".join(subset))
              return
          # Choice 1: include word i
          subset.append(words[i])
          visit(i + 1)
          subset.pop()
          # Choice 2: exclude word i
          visit(i + 1)
      visit(0)
      return res
  

  Question 2 Thesaurusly

  LeetCode 1258 LeetCode 17

  LeetCode 1258. Synonymous Sentences • Similar to LeetCode 17. Letter Combinations of a Phone Number

  Given a non-empty string, sentence, and a non-empty map, synonyms, where each key is a single word in the sentence, and its value is a list of synonyms, return all possible sentences that can be created by replacing the words in the sentence with their synonyms. Words without synonyms should remain unchanged. The input sentence only contains lowercase letters and spaces, while the words in synonyms only contain lowercase letters. The order of the generated sentences in the output does not matter.

  • Example: sentence = "one does not simply walk into mordor" synonyms = { "walk": ["stroll", "hike", "wander"], "simply": ["just", "merely"] }
  • Output: ["one does not just stroll into mordor", "one does not just hike into mordor", ...]

  Note on LeetCode 1258

  The actual LeetCode 1258 problem is slightly more complex. Instead of a pre-built map, it provides a list of synonym pairs (e.g., [["happy", "joy"], ["joy", "cheerful"]]). Because synonyms are transitive, you must first group connected words using a Graph (BFS/DFS) or a Disjoint Set (Union-Find) to build the complete synonym dictionary before backtracking. This simplified version focuses purely on the backtracking step.

  Solution 2 Thesaurusly

  We can build the output sentences one word at a time. For words without synonyms, keeping the word the same is the only choice. For words with synonyms, we have a choice per synonym.

  python

  Copy

  def generate_sentences(sentence, synonyms):
      words = sentence.split()
      res = []
      cur_sentence = []
      def visit(i):
          if i == len(words):
              res.append(" ".join(cur_sentence))
              return
          if words[i] not in synonyms:
              choices = [words[i]]
          else:
              choices = synonyms.get(words[i])
          for choice in choices:
              cur_sentence.append(choice)
              visit(i + 1)
              cur_sentence.pop() # Undo change
      visit(0)
      return res
  

  The depth of the decision tree is n, the number of words in sentence. The maximum branching factor is the maximum number of synonyms of any word. The total runtime is O(n * L * w), where w is the maximum length of an output sentence.

  Question 3 Jumping Numbers LeetCode 1215

  LeetCode 1215. Stepping Numbers

  A jumping number is a positive integer where every two consecutive digits differ by one, such as 2343. Given a positive integer, n, return all jumping numbers smaller than n, ordered from smallest to largest.

  • Example: n = 34
  • Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32]
  Solution 3 Jumping Numbers

  We start with no digits, and we add digits one by one, respecting the 'jumping number' constraint. There are two things to keep in mind:

  1. The numbers at non-leaf nodes are valid jumping numbers too, so we need to add to the global output array at every node, not only the leaves.
  2. The backtracking visit order is not the sorted order. We can add a sorting postprocessing step at the end.

  python

  Copy

  def jumping_numbers(n):
      res = []
      def visit(num):
          if num > n:
              return
          res.append(num)
          last_digit = num % 10
          if last_digit > 0:
              visit(num * 10 + (last_digit - 1))
          if last_digit < 9:
              visit(num * 10 + (last_digit + 1))
      for num in range(1, 10):
          visit(num)
      return sorted(res)
  

  Reusable Idea: EXTRACTING AND ADDING DIGITS In some problems, we need to handle integers digit by digit. The following loop extracts all the digits of x and returns them as an array, from least to most significant:

  python

  Copy

  while x > 0:
      arr.append(x % 10) # Extract the last digit.
      x = x // 10 # Remove the last digit.
  

  We can reassemble x like this: x = x * 10 + digit.

  Question 4 IKEA Shopping

  A magazine has rated every IKEA item from 1 to 10 in terms of style. We have gone to IKEA with a limited budget and the goal of maximizing the sum of style ratings of the items we buy. We also don't want to pick more than one of each item. We are given 3 things:

  • budget, a positive integer
  • prices, an array of n positive integers
  • ratings, an array of n positive floating-point numbers between 0 and 10 (inclusive)

  There are n items. Item i has price prices[i] and style rating ratings[i]. Return an array with the indices of the items that we should buy.

  • Example: budget = 20, prices = [10, 5, 15, 8, 3], ratings = [7.0, 3.5, 9.0, 6.0, 2.0]
  • Output: [0, 3] (With items 0 and 3, we get a rating sum of 13 without exceeding the budget.)
  Solution 4 IKEA Shopping

  This is a variation of the classic Knapsack problem, a subset-based optimization problem. We can start with an empty shopping cart, and make a decision for each item: pick it or not. We can prune subsets that exceed our budget. At the leaves, we check if the current subset has the best sum of ratings so far.

  python

  Copy

  def maximize_style(budget, prices, ratings):
      best_rating_sum = 0
      best_items = []
      n = len(prices)
      items = []
      def visit(i, cur_cost, cur_rating_sum):
          nonlocal best_items, best_rating_sum
          if i == n: # at leaves
              if cur_rating_sum > best_rating_sum:
                  best_rating_sum = cur_rating_sum
                  best_items = items.copy()
              return
          # Choice 1: skip item i.
          visit(i + 1, cur_cost, cur_rating_sum)
          # Choice 2: pick item i (if within budget).
          if cur_cost + prices[i] <= budget:
              items.append(i)
              visit(i + 1, cur_cost + prices[i], cur_rating_sum + ratings[i])
              items.pop() # undo pick
      visit(0, 0, 0)
      return best_items
  

  Question 5 White Hat Hacker

  You are trying to hack into an account (for good reasons, I'm sure). You know that the password:

  • has at least 1 and at most 10 letters,
  • uses only lowercase English letters,
  • does not repeat any letter.

  You have a script that tries to log in with a given password and returns a boolean indicating if it was successful. Write a function to find the password. You can call check_password(s) to check if s is the password.

  • Example: check_password("bc") returns True.
  • Output: "bc"
  Solution 5 White Hat Hacker

  The fact that the "password size" constraint is 10 is a trigger to use backtracking. We can generate all permutations of the alphabet, stopping at length 10. Non-leaf nodes are also potential passwords, so we can call check_password() for those partial permutations too.

  In the worst case, the number of check_password() calls will be huge, but backtracking allows us to systematically explore the space.

  python

  Copy

  def crack_password():
      alphabet = "abcdefghijklmnopqrstuvwxyz"
      
      def visit(current_pass):
          if len(current_pass) > 0:
              if check_password(current_pass):
                  return current_pass
          
          if len(current_pass) == 10:
              return None
              
          for char in alphabet:
              if char not in current_pass:
                  res = visit(current_pass + char)
                  if res: return res
          return None
  
      return visit("")
  

  Question 6 Count Unique Submultisets With Sum Zero LeetCode 40

  Similar to LeetCode 40. Combination Sum II

  A multiset is a set that allows repeated elements. A submultiset of a multiset S is another multiset obtained by removing any number of elements from S. We are given an array with n integers representing a multiset (it can have duplicates). Return the number of unique submultisets of S with sum 0, ignoring which position in S the values came from.

  • Example: S = [1, 1, -1, -1]
  • Output: 3. The unique submultisets with sum 0 are [], [1, 1, -1, -1] and [1, -1].
  Solution 6 Count Unique Submultisets With Sum Zero

  This is a counting problem, which is a trigger for trying to optimize with DP. However, finding just one subset with sum 0 is NP-complete, so we expect exponential time. Backtracking is the best we can do.

  The issue with typical subset backtracking is duplicates. The space complexity becomes exponential if we store all results to remove duplicates.

  Optimization: Instead of deciding individually for each element (pick/skip), our choice can be: "how many copies of this element should I pick?" In the implementation, we can start by building a frequency map mapping elements to how many times they appear in S.

  python

  Copy

  from collections import Counter
  
  def count_zero_submultisets(nums):
      counts = Counter(nums)
      unique_nums = list(counts.keys())
      res = 0
      
      def visit(i, current_sum):
          nonlocal res
          if i == len(unique_nums):
              if current_sum == 0:
                  res += 1
              return
  
          num = unique_nums[i]
          max_count = counts[num]
          
          # Choice: take 'c' copies of 'num'
          for c in range(max_count + 1):
              visit(i + 1, current_sum + c * num)
              
      visit(0, 0)
      return res # Includes the empty set
  

  Question 7 4-Directional Max-Sum Path

  Given an RxC grid of integers (which can be negative), grid, return the path from the top-left corner to the bottom-right corner with the largest sum. You can go in all four directions (diagonals not allowed), but you can't visit a cell more than once.

  • Example: grid = [[1, -4, 3], [-2, 7, -6], [5, -4, 9]]
  • Output: [[0, 0], [0, 1], [1, 1], [1, 0], [2, 0], [2, 1], [2, 2]] The maximum path is 1 -> -4 -> 7 -> -2 -> 5 -> -4 -> 9, which has sum 12.
  Solution 7 4-Directional Max-Sum Path

  This variation of Max-Sum Path cannot be optimized with DP—it is NP-complete. Backtracking is the best we can do.

  We iterate through the path we built so far to make sure we don't revisit cells. Or, we can do an additional work optimization and maintain a set of cells in the current path.

  python

  Copy

  import math
  
  def max_sum_path(grid):
      R, C = len(grid), len(grid[0])
      max_s = -math.inf
      visited = set()
      
      def visit(r, c, current_sum):
          nonlocal max_s
          if r == R - 1 and c == C - 1:
              max_s = max(max_s, current_sum)
              return
          
          visited.add((r, c))
          
          # Directions: up, down, left, right
          for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
              nr, nc = r + dr, c + dc
              if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in visited:
                  visit(nr, nc, current_sum + grid[nr][nc])
                  
          visited.remove((r, c))
          
      visit(0, 0, grid[0][0])
      return max_s
  

  Question 8 Escape With All Clues LeetCode 980

  Similar to LeetCode 980. Unique Paths III

  We are building an escape room puzzle where a player has to collect all the clues in a room to unlock the way out. The room is represented by a non-empty grid, room, consisting of walkable spaces (0), obstacles (1), and clues (2). The player starts on the top-left cell of the grid, which is guaranteed to be an open space, and can move to adjacent cells (diagonals not allowed). If it is possible to collect all the clues without repeating any cell, return an array with the list of cells in the shortest path to collect them, starting with [0, 0]. Otherwise, return an empty array. If there are multiple shortest paths, return any of them. It is guaranteed that there is at least one clue.

  • Example: room = [[0, 2, 0], [0, 0, 2]]
  • Output: [[0,0], [1,0], [1,1], [1,2], [2,2]] (One valid path)
  Solution 8 Escape With All Clues

  This is NP-complete! It's a mashup of TSP and Hamiltonian Path. To succeed, we must address the invalidating scenarios.

  The problem asks for the shortest path, which is a trigger for BFS. But wait—a shortest path algorithm heads straight to its destination, which might block its own path in the future.

  Let's follow a backtracking approach. We generate every path from the starting point that does not revisit any cells (but also avoiding obstacles). Our leaves are paths that contain every clue. While we generate all paths, we keep track of the shortest path so far in a 'global' variable. We can prune paths that hit dead ends.

  python

  Copy

  def escape_room(room):
      R, C = len(room), len(room[0])
      total_clues = sum(row.count(2) for row in room)
      min_path = None
      
      # path is list of [r, c]
      def visit(r, c, collected_clues, path):
          nonlocal min_path
          
          # Pruning: if current path is already longer than best found, stop
          if min_path and len(path) >= len(min_path):
              return
  
          # Check if we have all clues
          if collected_clues == total_clues:
              min_path = list(path)
              return
  
          # Try 4 directions
          for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
              nr, nc = r + dr, c + dc
              if 0 <= nr < R and 0 <= nc < C and room[nr][nc] != 1:
                  if [nr, nc] not in path: # Avoid cycles
                      new_clues = collected_clues + (1 if room[nr][nc] == 2 else 0)
                      path.append([nr, nc])
                      visit(nr, nc, new_clues, path)
                      path.pop()
  
      visit(0, 0, 1 if room[0][0] == 2 else 0, [[0, 0]])
      return min_path if min_path else []
  

  Key Takeaways

  Conceptually, we tried to demystify backtracking by presenting it as a variation of an algorithm we already know: tree-based DFS. Our main advice is to always draw the decision tree in advance, which should make traversing it more intuitive.

  When it comes to the implementation, perhaps the most confusing part is recursively making changes to a global state and then undoing it (see the reusable idea: 'Modify -> Recurse -> Undo'). Hopefully, the step-by-step illustrations help you understand it, but if that's still confusing, you can always copy the state at each node.

  Backtracking Triggers:

  • Problems with maximum input sizes in the lower 2-digits.
  • Enumeration problems or problems with exponential-sized outputs in general.
  • NP-complete problems, especially optimization ones.
  • Games and puzzles (like N-queens, sudoku, knight's tour problem).
  • Subset-based or permutation-based problems.
  • Problems where you'd think of using DP but there are no overlapping subproblems.