Backtracking
Solution Space Trees
Count: 10
In the Overview section, we use Depth-First Search to explore all valid root-to-leaf paths in a binary tree that we are given. In most backtracking problems, we won't be given an explicit tree to traverse. Instead, our algorithm needs to construct the tree based on the problem.
Example: Letter Combinations of a Phone Number
DESCRIPTION
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
2: "abc"
3: "def"
4: "ghi"
5: "jkl"
6: "mno"
7: "pqrs"
8: "tuv"
9: "wxyz"Example:
Input:
"23"Output:
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]We can think about solving this problem incrementally, using the input "23" as an example.
We start with an empty string, and form all possible combinations that can be made using the first digit.
"2" -> ["a", "b", "c"]
Now we take each of these combinations above and add the letters corresponding to the second digit, "3".
Since "3" maps to "def", we add "d" to "a", "b", and "c", then "e" to "a", "b", and "c", and finally "f" to "a", "b", and "c".
"23" -> ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
If we were to visualize this process a tree, it would look like this, where the leaf nodes represent the final combinations:
This tree conceptually represents the "solution space" of all possible letter combinations of the phone number. If we can traverse this tree, we can find all valid combinations.
So how do we do so without an explicit tree to traverse? Let's break it down.
Writing a Backtracking Algorithm
Now that we can visualize the "solution-space" tree, our next step is to write a backtracking solution which uses depth-first search to explore all possible paths in the tree.
Defining the Recursive Function
Conceptually, each node in the tree corresponds to a single recursive call. Each recursive call will make additional recursive calls, which are represented by the edges in the tree.
To define our recursive function, we need to figure out what information we need to pass to each recursive call / node so that it can reach its neighbors, as this determines the parameters of our recursive function.
Let's illustrate with the example of "23":
At the root node, we start with an empty string. The children of the root node are "a", "b", and "c", which correspond to the digit 2. So we can label the root node with 2 parameters, the empty string, and 0, which represents the index of the digit in the input phone number we are currently processing.
This suggests that our recursive function should have two arguments: the current combination, and the index of the digit we are currently processing.
Solution
Python
def backtrack(path, idx):
Next, we need to figure out how to explore the neighbors of the root node, which are "a", "b", and "c". We can get "a", "b", "c" by iterating over the letters corresponding to our digit "2", and adding each letter to our current combination (which right now is the empty string). For each of these letters, we make a recursive call with the updated combination and the next digit in the phone number.
Since each edge in our tree corresponds to a recursive call, this suggests that the body of our recursive function should iterate over the letters corresponding to the current digit, and make a recursive call for each letter with the updated combination and the next digit in the phone number.
Solution
Python
def backtrack(path, idx):# base case...for letter in phone[digits[idx]]:backtrack(path + letter, idx + 1)
Those recursive calls lead us to the last level of the tree, which are the leaf nodes. At the leaf nodes, we should add the current combination to our list of valid combinations.
We know we are at a leaf node when the index of the digit we are processing is equal to the length of the phone number. So we can add a base case to our recursive function to check if the index is equal to the length of the phone number. If it is, we add the current combination to our list of valid combinations.
Solution
Python
def backtrack(path, idx):# base case: we have reached a leaf nodeif idx == len(digits):result.append(path)returnfor letter in phone[digits[idx]]:backtrack(path + letter, idx + 1)
Finally, in the main function, we kick off the call to our recursive function with the empty string and the index 0 (the root node of our tree).
Solution
Python
def letterCombinations(digits):phone = {"2": "abc","3": "def","4": "ghi","5": "jkl","6": "mno","7": "pqrs","8": "tuv","9": "wxyz"}def backtrack(path, idx):if idx == len(digits):result.append(path)returnfor letter in phone[digits[idx]]:backtrack(path + letter, idx + 1)result = []if digits:backtrack("", 0)return result
Summary
The first step in solving a backtracking problem is to visualize the solution-space tree.
- Each node in the solution-space tree corresponds to a single recursive call.
- The parameters of the recursive function correspond to the information needed to reach the neighbors of a node.
- The body of the recursive function should iterate over the neighbors of a node and make recursive calls for each neighbor.
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Calculating the time and space complexity of a backtracking algorithm depends on the structure of the solution-space tree. Here are the general guidelines:
- Depth of the tree: Often the size of the input (for our phone number problem, this is n)
- Branching factor: The number of recursive calls made in the body (for our problem, this is 4)
For our phone number problem:
- Depth = length of phone number (n)
- Branching factor = 4 (each digit maps to at most 4 letters)
The tree structure has:
- 1 node at depth 1
- 4 nodes at depth 2
- 4² nodes at depth 3
- ...
- 4ⁿ nodes at depth n (leaf nodes)
The total number of nodes is 1 + 4 + 4² + ... + 4ⁿ, which is asymptotically O(4ⁿ).
Solution-Space Tree Examples
The solution-space tree will look different for each backtracking problem, but one common type is a binary tree, where each node in the tree represents a "choose" or "don't choose" decision at that level.
This tree can be used to generate all possible subsets of a list of integers, which we breakdown below:
DESCRIPTION
Given a set of distinct integers, nums, return all possible subsets (the power set), without duplicates.
Example:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
The solution-space tree for this problem is a binary tree. Each node in the binary tree represents a different subset of the input.
So how do we go from one node to its children in this tree? Each level in the tree corresponds to a different element in the input set, and each child node corresponds to either including (left) or excluding (right) the current element in the subset represented by the parent node.
At the root node, where current subset = [], and the current element is 1:
- Left Child: We take the current subset and include 1. This gives us the subset [1].
- Right Child: We take the current subset and exclude 1. This gives us the subset [].
For the subset [1], we repeat the process, now with current element 2:
- Left Child: We take the current subset and include 2. This gives us the subset [1, 2].
- Right Child: We take the current subset and exclude 2. This gives us the subset [1].
Given that information, try writing a backtracking solution for this problem on your own!
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.