First of all, we have to acknowledge that it is very difficult to come up with the exact bound for runtime in backtracking as we have varying conditions of pruning wasteful explorations/recursions.
However, we can always come up with the upper/loose bound for runtime and explain our thought process of how to get that runtime.
In general, we can calculate/estimate the maximum number of outputs that will be generated from the backtracking algorithm (i.e., treating as if it's a brute force solution and ignore all optimizations of pruning to calculatate the upper runtime).
If we can find the max number of outputs, we can easily draw out the decision tree and find the total number of nodes in it. The total number of nodes will be the runtime we will consider (as that will be the brute force solution).
From the decision tree perspective, we basically want to find the branching factor and its height.
Let's look at some of the popular questions.
Permutations
Permutations = ordering of numbers.
If we are given N numbers to order them: _ _ ... _ _
For the 1st number, we have N choices to select
For the 2nd number, we have N-1 choices to select (since we have used 1 element in the previous number)
For the 3rd number, we have N-2 choices to select (since we have used 2 elements in the previous number)
... For the Nth number, we have 1 choice to select.
This gives us the maximum number of outputs of (N)(N-1)(N-2)...(1) => N!
In a decision tree, this would correspond to N! number of leaf nodes:
[Without delving into mathematical details, we can assume N! maximum number of outputs always refer to the number of leaf nodes]
Since it takes N steps to get to each leaf node (i.e., height of the decision tree), we would have (N * N!) nodes in total.
And for leaf nodes, we take O(N) operation to copy over (to terminate).
Hence, it takes us O(N * N!) to get to leaf nodes (i.e., to travel all nodes), and for each of N! leaf nodes, we need O(N) operation to copy over.
=> O(N * N! + N * N!)
=> O(N * N!)
Combinations
Similarly, we have nCk (n choose k) number of maximum outputs, taking k steps to reach each of them, and k steps to copy them over
=> O(k * nCk)
Subsets
Given N numbers, we need to find all subsets.
Every single number will have a chance to be included or not (2 choices for each number)
Ex) [1 2 3]:
1 _ _ => [1] (2 & 3 excluded)
_ 2 _ => [2] (1 & 3 excluded)
1 2 _ => [1, 2] (3 excluded)
...and so on.
This means we have the maximum number of outputs of 2^N.
Note these are not leaf nodes! Every single node is part of the outputs. Just draw out a simple decision tree.
[Without delving into mathematical details, from this point onwards, we can assume if we have a constant number of branching factor C (2 in this case), C^H is the total number of nodes where H = height of decision tree]
Hence, we have a total of 2^N nodes, each of which takes at most O(N) operation to copy over
=> O(N * 2^N)
So from the observations above, we can assume the following as handy facts:
S1. If the branching factor is constant C (i.e., if we have a fixed number of choices C), the total number of nodes is C^H where H is the height or the number of times we have to repeat.
S2. If the branching factor is not constant and has the (N)(N-1)...(1) pattern, the total number of nodes is N! * H
S3. If the branching factor is not constant and doesn't have a particular pattern, we can always come up with the upper bound constant C and get C^H total number of nodes (as we will see in later problems).
N-Queens
Given N * N board, return all possible solutions.
We are checking row by row, and see where in each row, we can place the queen correctly.
In the first row, we have N choices to place the queen (since there are N columns in each row).
Then, we have (N-1) choices to place the queen in the next row (since there are N columns in each row, and one of them has been taken in the first row).
... and so on.
This gives us the maximum number of outputs (more like possibilities in this case) of N! (and they are leaf nodes by S2).
It took N steps to reach each leaf node => N * N! is the toal number of nodes
And there will be at most N! solutions (as they are the leaf nodes) to copy over => O(N^2 * N!)
=> O(N * N! + N^2 * N!) => O(N^2 * N!)
[Note we did not take into account the optimization of pruning wasteful explorations, but we are certain it will never be worse than this runtime].
Letter Combinations of a Phone Number
Given a number of N digits, we want to map the number (ex. 23) to the possible combinations of letters (ex. "ad", "ae", "af", "bd", ...).
Each digit maps to 3 or 4 letters
Ex)
8 => t,u,v
9 => w,x,y,z
Hence, for each digit, we have 3-4 letters (choices) to choose from. By S3, since it's not constant, we will choose the upper constant (4), and assume there are 4 letters (choices) for each digit (i.e., we have up to 4 choices).
How many times are we doing this (i.e., what's the height)? N times.
It takes O(N) operation to copy each of them.
=> O(N * 4^N)
Combination Sum
We want to find the combinations of numbers that make up the target number.
Let N = # of digits we can choose.
Note we can re-use the same element. Hence, we have exactly N choices for each digit of the combination.
Let M = maximum size of the combination.
Total number of nodes = N^M.
But we are also copying leaf nodes! # of leaf nodes = N^(M-1)
Copy operation = O(M)
Coping of leaf nodes => O(M * N^(M-1)) => O((M/N) * N^M)
=> O(max(1, M/N) * N^M)
For even tighter bound, check out: https://la60312.medium.com/leetcode-39-combination-sum-79df7114879a
Generate Parantheses
Given N pairs of parantheses, find all solutions.
There are 2N characters we have to fill. For each character, we have two choices "(" or ")".
The total number of nodes = 2^(2N) = 4^N
Copy opeartion = O(2N) = O(N)
=> O(N * 4^N)
[Again, we don't techincally copy all combinations, just the valid ones, but we are certain it will never be worse than this.]
Word Search
First of all, although this question uses the DFS pattern to explore, it is not DFS.
Why? Because we have to set it back to what it was after the recursions:
and therefore cannot keep track of visited cells for the next round of DFS.
This failure to keep track of visited cells makes the runtime go exponential instead of the usual DFS runtime of
O(|V| + |E| or N).
With that, let's calculate the runtime.
Given a word of length L, we need to find if they exist in the board.
For each letter, we are expanding into 4 recursion calls (creating 4 branches), until it finds all letters.
So one round of DFS() = O(4^L)
In the worst case, we may run DFS() for all cells (for inputs like board = [[A...A], [A...A], ... , [A...A]], word = "A...A")
=> O(M * N * 4^L)
Sudoku Solver
We assume a 9x9 board.
Given X number of empty cells, our task is to fill them between 1-9.
=> 9 choices, X numbers to fill
=> O(9^X)
Restore IP Addresses
We need to find the correct number for (N=4) parts of the IP address.
We have up to (M=3) choices per part (i.e., "23234" => "2", "23", "232")
This gives us M^N = 3^4 total number of nodes.
We copy at most M^(N-1) nodes.
Copy operation takes at worst O(M * N).
Hence, we get O(M^N + (M * N) (M ^ (N-1)) = O(M^N + N * M^N) = O(N * M^N)
=> O(1)
Target Sum
We want to use all numbers in the array and assign + and - to each of them. If they add up to target, it's a solution.
We have two choices (+ and -) to assign to each number, and there are N numbers.
There is no copy or any > O(1) operation used in the algorithm, which brings the runtime to be
=> O(2^N)
Quick Note: Backtracking would cause TLE in this problem since there are many repeated recursive calls that DO NOT have to be run, which means it's a perfect candidate to be solved with DP.
Note 2: You can use cache/memoization to drastically improve the runtime for CERTAIN test cases, but not all. Check my comment here as the official solution is incorrect: https://leetcode.com/problems/target-sum/solutions/455024/dp-is-easy-5-steps-to-think-through-dp-questions/comments/1761035
Letter Case Permutation
Assume a string of size L.
We have two choices per character (uppercase, lowercase).
In the worst case, we may be changing all characters and therefore copy all combinations of those.
=> O(2^L * L)
Lastly, the height of the decision tree + any other auxiliary space used in the algorithm is the space complexity.
Bonus: How do we implement a backtracking algorithm? [Skip If Not Needed - For Beginners]
As we have seen in the runtime analyses above, backtracking exists to find all possible solutions with the given set of choices.
To find all such solutions, we need to explore with the given set of choices. If we obey this rule, the coding portion becomes a breeze.
Before we take a look into the implementation details, let us remind ourselves that we use recursion in backtracking because there is a lot of the same work that needs to be repeated for each choice.
Backtracking Template
def recurse():
# base case
# exploration with the given choices
# explore
# recurse
# backtrackIn exploration with the given choices, we have explore, recurse, and backtrack.
explore ensures the state we pass down to the next recursive call (recurse) is correctly set.
backtrack ensures that the state is set back to what it was before recurse happened (as if recurse had never happened!)
Why are we doing this? Because we want to explore other choices!
We are all equipped now. Let’s tackle the problems.
Permutations
Again, after realizing it's a backtracking question, we need to find how to explore with the given set of choices.
Let's start with an example.
Given [1,3,8], find its all permutations ([8,3,1],[3,1,8], etc).
For index = 0, we can choose 1,3,8.
Choose 3.
Then we have 2 choices (1,8) for index = 1.
Choose 1.
Then we are left with one choice of 8 for index = 2.
=> [3,1,8]
It's clear that we need to make sure the chosen element is excluded from the list of choices for the next selection.
(i.e., Choose 3, then we need to make sure we choose from [1,8]).
How do we do that? Explictly slice the array such that the chosen element is excluded (ex. Choose 3. Then [1,3,8] => [1,8]).
def permute(self, nums: List[int]) -> List[List[int]]:
N = len(nums)
result = []
def recurse(soFar, choices):
# base case
if len(soFar) == N:
result.append(soFar[:])
return
# exploration with given choices
for x in range(len(choices)):
# explore
soFar.append(choices[x])
# recurse
recurse(soFar, choices[:x] + choices[x+1:])
# backtrack
soFar.pop()
recurse([], nums)
return resultNotice we changed nothing from the template. After we have an idea of how pass down the choices, it's pretty easy to code it up.
But if you do this in the interview, you will fail. Because you are making a new array of choices in every call, taking extra space and time. You are not taking the full advantage of the backtracking algorithm structure.
Let's implictly slice the array. How?
- Use pointer instead of passing the whole array
- Swap the chosen element with the first element of the array.
Why are we swapping with the first element? Because by swapping with the first, the chosen element is now conveniantly located at the start of the array, and all other elements we need to include are located to its right. Then, we can simply skip the first element over by incrementing the pointer.
Look at an example below:
Given [1,3,8,5,6].
We want to choose 8. Then swap 8 with 1 to get
=> [8,3,1,5,6].
Skip the first element by passing down the the pointer where pointer=start+1 so that we have
=> [1,3,5,6]
(8 is succesfully excluded!)
def permute(self, nums: List[int]) -> List[List[int]]:
N = len(nums)
result = []
def recurse(soFar, start):
# base case
if len(soFar) == N:
result.append(soFar[:])
return
# exploration with given choices
for x in range(start, N):
# explore
soFar.append(nums[x])
nums[x], nums[start] = nums[start], nums[x] # swap
# recurse
recurse(soFar, start + 1)
# backtrack
soFar.pop()
nums[x], nums[start] = nums[start], nums[x] # swap back
recurse([], 0)
return resultPermutations II
The input may have duplicates: [4,2,2]
If there are duplicates, we will be selecting the same choice, creating duplicates in the result.
For example, for index = 0, the original algorithm would choose 4, then 2, then 2 again:
[4, _ , _]
[2, _ , _]
[2, _ , _]
To avoid this, we have 2 options:
- Repicture the given input array as a hash table of keys and the number of their occurences => Keys are unique and therefore traversing keys will guarantee uniqueness
- Sort the array and ignore all duplicates => We can't swap anymore then, as it will mess up the order. So we will have to create new arrays every time.
I do not recommend 2, becaus we have to create new arrays of length k where k = n-1, n-2, ... 1. => O(N-1) * O(N-2) * ... O(1) => O(N-1)! => O(N-1 * (N-1)!) in total.
The overall runtime is not impacted, since it's still O(N * N!). But regardless, it's too computationally heavy.
Always go with 1, and create the hash table of counters.
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
HT = Counter(nums)
N = len(nums)
result = []
def recursion(soFar):
# base case
if len(soFar) == N:
result.append(soFar[:]) # new copy
return
# exploration with the given choices
for key in HT:
if HT[key] == 0: continue
# explore
soFar.append(key)
HT[key] -= 1 # indicate it's used
# recurse
recursion(soFar)
# backtrack
soFar.pop()
HT[key] += 1
recursion([])
return result
Combinations
Return all combination of size k from [1,n].
Ex) n=3, k=2 => [1,2,3] (k=2) => [1,2], [1,3], ...
What's different from permutations? [1,3] = [3,1]
To achieve this, we can simply return those in ascending order (ex. [1,3] and not [3,1]).
To return only the ascending order of elements, we can initially sort the array, and make sure for each chosen number, we only give the numbers to the right of it for the choices of the next selection.
Ex) [1,2,3,4] (k=2). Choose 2, give [3,4] as the choices for the next selection to achieve [2,3], [2,4]
But do we need to explictly sort the array? NO! Because we can always assume the input is of the form [1...n] and therefore for x in range(start, n) suffices.
Note we can make a little optimization by traversing up until the last element that has (k - len(soFar)) elements to its right.
Hence, n - (k - len(soFar)) is the last element we can include.
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
def recurse(soFar, start):
# base case
if len(soFar) == k:
result.append(soFar[:])
return
# explore with the given choices
end = n - (k - len(soFar))
for x in range(start, end+1):
# explore
soFar.append(x+1)
# recurse
recurse(soFar, x + 1)
# backtrack
soFar.pop()
recurse([], 0)
return result
Combination Sum
[2,3,6,7] (t=7) => [7], [2,2,3]
Note we can use the same element more than once.
Which creates an interesting test case such as below:
[2,4,6]:
2 + 2 + 2 + 2 + 2 + 2
2 + 2 + 2 + 2 + 4
2 + 2 + 2 + 4 + 2
2 + 2 + 2 + 6
...
If we sort the array, it's clear when we can terminate immediately. If the currentSum >= target, we backtrack and try a different choice. Just like below:
2 + 2 + 2 + 2 + 2 + 2 (target! let's backtrack!)
2 + 2 + 2 + 2 + 4 (try a different choice, 4, another target!)
Since we can use the same element more than once, we can pass the current element for next selection of choices.
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
N = len(candidates)
candidates.sort()
result = []
def recurse(soFar, sum, currIndex):
# base case
if sum == target:
result.append(soFar[:])
return True
if sum > target:
return True
# exploration with the given choices
for x in range(currIndex, N):
# explore
soFar.append(candidates[x])
sum += candidates[x]
# recurse
isGreaterOrEqual = recurse(soFar, sum, x)
# backtrack
soFar.pop()
sum -= candidates[x]
if isGreaterOrEqual:
return False
recurse([], 0, 0)
return result
Just a special note to recurse(soFar, sum, x). Since we are dealing with combinations and the array is sorted, we need to make sure we only pass elements to its right (hence x+1 and not start+1) and since we also want to include the current element, it's x and not x+1.
Combination Sum II
This time, we can only use the element once. Therefore, we need to sort and pass x+1 to pass only its right elements.
Note the input could contain duplicates! Like how we explored in Permutations II, we can go with (2) approach since the array is already sorted.
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
N = len(candidates)
result = []
def recurse(soFar, sum, start):
# base case
if sum >= target:
if sum == target:
result.append(soFar[:])
return True
# explore with the given choices
for x in range(start, N):
if x > start and candidates[x] == candidates[x-1]: # avoid duplicates!
continue
# explore
soFar.append(candidates[x])
sum += candidates[x]
# recurse
isEqualOrGreater = recurse(soFar, sum, x + 1)
# backtrack
soFar.pop()
sum -= candidates[x]
if isEqualOrGreater:
return False
recurse([], 0, 0)
return result
Combination Sum III
We want to find combinations of size k that sum up to n using numbers 1-9.
This is combinations => we want to sort the array and pass its right elements only (i.e., x+1). We don't need to explictly sort the array because we can always traverse from 1 to 9.
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
result = []
def recurse(soFar, sum, start):
# base case
if len(soFar) == k:
if sum == n:
result.append(soFar[:])
return True
return False
# exploration with the given choices
for x in range(start, 9):
# explore
soFar.append(x+1)
sum += (x+1)
print(soFar)
# recurse
isFound = recurse(soFar, sum, x+1)
# backtrack
soFar.pop()
sum -= (x+1)
if isFound:
return False
return False
recurse([], 0, 0)
return resultSubsets
We want to find all subset. Note subsets = combinations, and hence [1,3] = [3,1].
Like in combinations, we want to restrict the choices to the elements to the right of the current element. Do we need to sort? No, we only do it for duplicates in the input. This question has said there are no duplicates in the input.
def subsets(self, nums: List[int]) -> List[List[int]]:
N = len(nums)
result = [[]]
def recurse(soFar, start):
# base case
if start == N:
return
# exploration with the given choices
for x in range(start, N):
# explore
soFar.append(nums[x])
result.append(soFar[:])
# recurse
recurse(soFar, x + 1) # x + 1 ensures that we only check out the elements to the right of it.
# backtrack
soFar.pop()
recurse([], 0)
return result
Notice we are adding for every new choice selected, since we are interested in all sizes.
Subsets II
We now have duplicates in the input. Let's sort.
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = [[]]
def recursion(soFar, start):
# exploration with the given choices
for x in range(start, len(nums)):
if x > start and nums[x] == nums[x-1]:
continue
# explore
soFar.append(nums[x])
result.append(soFar[:])
# recurse
recursion(soFar, x + 1)
# backtrack
soFar.pop()
recursion([], 0)
return resultNotice we removed base case, because it's got no use. But you can always add it back if you want to make it explicit.
N Queens
We have N rows to place each queen. One of the benefits of backtracking algorithm is that if we can determine a certain path is useless/wasteful, we can prune such exploration. This is usually done by isValid() where it checks (if it can) against a set of constraints. We must always do this if we can so that we can avoid wasteful explorations.
def solveNQueens(self, n: int) -> List[List[str]]:
boards = []
board = [["." for x in range(n)] for y in range(n)]
def isValid(r,c):
# check same col
for x in range(n):
if board[x][c] == 'Q':
return False
# check diagnols
x,y = r,c
while x >= 0 and y >= 0:
if board[x][y] == 'Q':
return False
x-=1
y-=1
x,y = r,c
while x < n and y < n:
if board[x][y] == 'Q':
return False
x+=1
y+=1
x,y = r,c
while x < n and y >= 0:
if board[x][y] == 'Q':
return False
x+=1
y-=1
x,y = r,c
while x >= 0 and y < n:
if board[x][y] == 'Q':
return False
x-=1
y+=1
return True
def recurse(r):
# base case
if r == n:
boards.append(["".join(row) for row in board])
return
# exploration with the given choices
for c in range(n):
if not isValid(r,c):
continue
# explore
board[r][c] = 'Q'
# recurse
recurse(r+1)
# backtrack
board[r][c] = '.'
recurse(0)
return boardsLetter Combinations of a Phone Number
Given a number, map to corresponding letters. For each digit, we have a set of choices. Simply repeat that work.
def letterCombinations(self, digits: str) -> List[str]:
if digits == "": return []
mapper = {
"2" : "abc",
"3" : "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
result = []
N = len(digits)
def recurse(soFar, digitIndex):
# base case
if digitIndex == N:
result.append("".join(soFar))
return
d = digits[digitIndex]
letters = mapper[d]
# exploration with the given choices
for letter in letters:
# explore
soFar.append(letter)
# recurse
recurse(soFar, digitIndex + 1)
# backtrack
soFar.pop()
recurse([], 0)
return result
Generate Parentheses
We are given two choice "(" and ")" at each index. But there are constraints to it that we can check to prune wasteful explorations just like in N-Queens.
def generateParenthesis(self, n: int) -> List[str]:
result = []
def recurse(open, close, currentString):
# base case
if len(currentString) == n * 2:
result.append("".join(currentString))
return
# exploration with the given choices
if open < n:
# explore
currentString.append("(")
# recurse
recurse(open + 1, close, currentString)
# backtrack
currentString.pop()
if open > close:
# explore
currentString.append(")")
# recurse
recurse(open, close + 1, currentString)
# backtrack
currentString.pop()
recurse(0,0,[])
return result
Word Search
This question requires us to explore in a DFS manner. The backtracking portion is that we have to set it back to what it was as if DFS() never happened
def exist(self, board: List[List[str]], word: str) -> bool:
MR = len(board)
MC = len(board[0])
def DFS(r,c,charAt):
# bound check
if r < 0 or c < 0 or r == MR or c == MC: return False
# visited check
if board[r][c] == '.': return False
# additional check
if board[r][c] == word[charAt]:
if charAt == len(word) - 1:
return True
# mark as visited
board[r][c] = '.'
res = DFS(r-1,c,charAt+1) or DFS(r+1,c,charAt+1) or DFS(r,c-1,charAt+1) or DFS(r,c+1,charAt+1)
# backtrack after we are done
board[r][c] = word[charAt]
return res
return False
for r in range(MR):
for c in range(MC):
if board[r][c] == word[0]:
# explore
if DFS(r,c,0): return True
return FalseSudoku Solver
Given X number of empty cells. We have to fill them with choices 1-9 while satisfying the constraints.
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
MR = len(board)
MC = len(board[0])
emptyCells = []
def findEmptyCells():
for r in range(MR):
for c in range(MC):
if board[r][c] == '.':
emptyCells.append((r,c))
findEmptyCells()
def isValid(val, cellIdx):
r,c = emptyCells[cellIdx]
# check row
for x in range(MC):
if board[r][x] == val:
return False
# check col
for x in range(MR):
if board[x][c] == val:
return False
# check subbox
x = (r // 3 * 3)
y = (c // 3 * 3)
for i in range(x, x+3):
for j in range(y, y+3):
if board[i][j] == val:
return False
return True
def recurse(cellIdx):
# base case
if cellIdx == len(emptyCells):
return True
# exploration with the given choices
for val in range(1, 10):
val = str(val)
if isValid(val, cellIdx):
# explore
r,c = emptyCells[cellIdx]
board[r][c] = val
# recurse
isFound = recurse(cellIdx + 1)
# backtrack
if isFound:
return True
else:
board[r][c] = '.'
return False
recurse(0)Restore IP Addresses
Each IP block has 3 choices (one of length 1, 2, and 3) in the string, which will be repeated 4 times.
def restoreIpAddresses(self, s: str) -> List[str]:
result = []
def isValid(ipBlock):
return int(ipBlock) >= 0 and int(ipBlock) <= 255
def recurse(soFar, start):
# base case
if len(soFar) == 4:
if start == len(s):
result.append(".".join(soFar))
return
# exploration with the given choices
for x in range(start, start+3):
if x == len(s): break
ipBlock = s[start:x+1]
if len(ipBlock) > 1 and ipBlock[0] == '0': break
if isValid(ipBlock):
# explore
soFar.append(ipBlock)
# recurse
recurse(soFar, x + 1)
# backtrack
soFar.pop()
recurse([], 0)
return resultLetter Case Permutation
For each letter, we have 2 choices (upper and lower).
def letterCasePermutation(self, s: str) -> List[str]:
toChange = []
for x in range(len(s)):
if s[x] >= '0' and s[x] <= '9':
continue
toChange.append(x)
result = []
def recurse(soFar, idx):
# base case
if idx == len(toChange):
result.append("".join(soFar))
return
sIdx = toChange[idx]
# exploration with the given choices
for char in [s[sIdx].upper(), s[sIdx].lower()]:
# explore
soFar[sIdx] = char
# recurse
recurse(soFar, idx + 1)
# backtrack
soFar[sIdx] = s[sIdx]
recurse(list(s), 0)
return resultBonus: Exploration Tips/Hacks
- Keep track of
startpointer and swap with the first number to implictly slice the array [Permutations] - If input has duplicates, create a hashtable (Counter) of keys and the number of their occurences [Permutations II]
- If input has duplicates, you can also sort and ignore duplicates (given that it doesn't use the swap technique like in 1) [Combination Sum II, Subsets II]