Introduction
Sometimes, an efficient solution (polynomial) time is just not possible. There are questions where the solution space is exponential, hence the fastest algorithm must be exponential time.
Backtracking is often utilized when we need to enumerate through all possibilities. We try every single final result, by trying every individual choice at every step, and if it is valid we append it to our final list.
A good example is computing all subsets of a list. (subset is any selection of elements from an array, including no elements) Aka. return the power set of a list. Since we can either use or not use any particular element, there are 2^n subsets. (2 choices at each decision point) There is no efficient algorithm for this - we have to enumerate through all 2^n possibilities as that is the desired result.
The key with backtracking is a solid understanding of recursion. How can we build a solution of size n, using an algorithm for size n-1?
We maintain a global variable 'curr', indicating the current array we are creating. If we have tried all options/elements of the array (i == n) we add this current array to our final list of arrays 'res'. Otherwise, we try all choices j from i to n-1. We try choice j, and then recursively backtrack on the remaining options from j+1 to n-1. After we finish all those possibilities, we want to try another choice than j. So we pop j from curr, and continue iterating over the other options.
We start the backtrack at index 0 to get the whole array, and then return res.
Backtracking Template
The general backtracking template:
Time complexity is generally exponential (O(2^n) for subsets) or factorial O(n!) (for permutations/combinations). The template above is O(n*2^n) since we have 2^n subsets and each subset has up to n length.
Correctness is obvious since backtracking is a brute force enumeration. For certain problems you just have to be careful when optimizing the template, (pruning, etc) that these optimizations are correct.
O(n*2^n) for subsets, O(n*n!) for permutationsO(n*2^n) or O(n*n!)General Template
def f(self, s: str) -> List[List[int]]:
n = len(s)
res = []
curr = []
def backtrack(i):
if i == n:
res.append(curr.copy()) # base case: this is valid so add to res
# NEED THIS curr.copy()... or else all arrays are empty in res...
# because it appends the REFERENCE of curr. (which eventually becomes empty)
else:
for j in range(i, n): # try all choices
curr.append(j) # append to curr
backtrack(j+1) # recurse on remaining
curr.pop() # undo append to curr, try next choices for j
backtrack(0)
return resSubsets Problems
Problems involving generating all subsets or power sets.
01SubsetsMedium
Given a list of numbers, return a list of all subsets.
Example:
- Input: nums = [1,2,3]
- Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
We apply the template. The only difference is for subsets, their size is not always of length n. So we need to also try the case, where we don't use nums[i]. This enables us to get all the subsets of length < n. To generate all subarrays, by definition, we either take or don't take the current value, and repeat.
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
subset = []
def backtrack(i):
if i == len(nums):
res.append(subset.copy())
else:
# use nums[i]
subset.append(nums[i])
backtrack(i+1)
subset.pop()
# do not use nums[i]
backtrack(i+1)
backtrack(0)
return resO(n*2^n)O(n*2^n)Recursive Thinking:
Subsets of [1,2] = (1 + subsets of [2]) and (nothing + subsets of [2]).
Subsets of [2] = {[], [2]}
Subsets of [1,2] = (1 + {[], [2]}) and ({[], [2]}) = {[1], [1,2], [], [2]}.
Keep this recursive thinking in mind to understand correctness. Don't just mindlessly apply the template.
02Subsets IIMedium
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = set()
subset = []
def backtrack(i):
if i == len(nums):
res.add(tuple(sorted(subset))) # NEED to sort the subset... or else we can
# get multiple permutations of the same combination... (ex. [1,2], [2,1])
else:
# use nums[i]
subset.append(nums[i])
backtrack(i+1)
subset.pop()
# do not use nums[i]
backtrack(i+1)
backtrack(0)
return list(res)
# Alternative: leverage Subsets solution
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
return list(set(tuple(sorted(A)) for A in subsets(nums)))O(n*2^n)O(n*2^n)We can apply the same template as before. The only thing is need to sort the subset, and make res a set. This is to prevent duplicates, where we consider permutations of the same subset as duplicates. (ie: [1,2], [2,1] are equivalent)
Combinations
Problems involving generating combinations of k elements.
01CombinationsMedium
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
We apply the template. The only difference is our termination condition is when our current array is length k as that finishes our combination. So this is basically getting all subsets of length k. (definition of a combination, as combination is basically equivalent to subset)
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
curr = []
def backtrack(i):
if len(curr) == k:
res.append(curr.copy())
else:
for j in range(i, n+1):
curr.append(j)
backtrack(j+1)
curr.pop()
backtrack(1)
return resO(n * C(n,k))O(n * C(n,k))Permutations
Problems involving generating all permutations.
01PermutationsMedium
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
We apply the same template. The only difference is instead of maintaining a new array 'curr', we can use the same original array nums, and just swap the values at index i and index j instead of adding them.
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
# swap
def backtrack(i):
if i == n:
res.append(nums.copy())
else:
for j in range(i, n):
nums[i], nums[j] = nums[j], nums[i]
backtrack(i+1) # has to be i+1, NOT j+1 !!!
nums[i], nums[j] = nums[j], nums[i]
backtrack(0)
return resO(n*n!)O(n*n!)Why does this work?
[1,2,3] -> [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
We first have j = i, so the swap does nothing and the first value is still 1. Then recursively, we want all permutations of the rest of the array [2,3].
So all permutations of [1,2,3] that start with 1 = [1] + permutations of [2,3].
permutations of [2,3] = [2,3], [3,2]
all permutations of [1,2,3] that start with 1 = [1] + ([2,3], [3,2]) = [1,2,3], [1,3,2].
Now, the recursion has finished, so we try moving 2 to the first value, and now 1 is in the second index. Then recursively, we want all permutations of the rest of the array [1,3].
So all permutations of [1,2,3] that start with 2 = [2] + permutations of [1,3].
… you get the idea.
N choices for index 0, n-1 choices for index 1, … 1 choice for index n-1.
02Permutations IIMedium
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = set()
# swap
def backtrack(i):
if i == n:
res.add(tuple(nums))
else:
for j in range(i, n):
nums[i], nums[j] = nums[j], nums[i]
backtrack(i+1) # has to be i+1, NOT j+1 !!!
nums[i], nums[j] = nums[j], nums[i]
backtrack(0)
return list(res)
# Alternative
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
return list(set(tuple(A) for A in permute(nums)))O(n*n!)O(n*n!)You know the drill. Same as Permutations but with a set to handle duplicates.
Combination Sum Problems
Problems involving finding combinations that sum to a target.
01Combination SumMedium
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
# this returns a unique list of combs without using a set, b/c the initial
# list is distinct integers.
# backtracking(i): tries all possible first choices of combs, from indicies [i, n-1]...
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
n = len(candidates)
curr = []
res = []
curr_target = target
def backtrack(i):
nonlocal curr_target
if curr_target < 0: return
if curr_target == 0:
res.append(curr.copy())
else:
# try to take every element. recurse on rest
for j in range(i, n):
curr.append(candidates[j])
curr_target -= candidates[j]
backtrack(j) # not j+1 !!! since we can re-use j
curr_target += candidates[j]
curr.pop()
backtrack(0)
return resO(n*2^n)O(n*2^n)We apply the template. This is the same as combinations/subsets. The only difference is we maintain a curr_target, that is basically target - sum(curr). So it refers to how much left we need to reach our target. If it is 0, we are done. That is the base condition of the backtracking. We can prune when curr_target < 0, since all numbers are positive, any further recursion is futile as sum(curr) is already > target. And our recursion is for index j not j+1, since we can re-use the same number multiple times.
Note: we don't actually need to maintain curr_target, since we can just compute sum(curr) every time, but this adds an additional O(n) factor to our runtime.
02Combination Sum IIMedium
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
curr = []
curr_target = target
n = len(candidates)
candidates.sort() # need this to skip multiple same values in order...
def backtrack(i):
nonlocal curr_target
if curr_target < 0: return
if curr_target == 0:
res.append(curr.copy())
else:
for j in range(i, n):
if j >= i+1 and candidates[j] == candidates[j-1]: continue # NEED THIS... skip dups
curr.append(candidates[j])
curr_target -= candidates[j]
backtrack(j+1)
curr_target += candidates[j]
curr.pop()
backtrack(0)
return resO(n*2^n)O(n*2^n)We use the same idea as before. A few differences: we can only use each number at most once, so we need to backtrack on j+1 instead of j. We also need to sort. This will prevent duplicates like [1,1,6] vs [6,1,1]. (imagine A = [1,1,6,1,1]) The naive version is actually too slow. We also need to prevent duplicates like [1,1,6] vs [1,1,6]. (imagine A = [1,1,1,6]) So we effectively use a 'while' loop like in Two Pointers, to move over the duplicates.
03Combination Sum IIIMedium
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers 1 through 9 are used.
- Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
curr = []
sum_ = 0
def backtrack(i):
nonlocal sum_
if len(curr) == k:
if sum_ == n:
res.append(curr.copy())
else:
for j in range(i, 10):
if sum_ + j > n:
break
sum_ += j
curr.append(j)
backtrack(j+1)
curr.pop()
sum_ -= j
backtrack(1)
return resO(C(9,k))O(k)We apply the template. We maintain a sum_ variable for the current sum of our list curr. Our base condition is if our list has length k and the sum is n we append to res.
We iterate over all digits from i to 9. (we either don't use or have already used the digits from 1 to i-1)
We can prune when sum_ + j > n, since adding j will make it impossible to reach n as all the digits are positive. This is an optimization, it doesn't affect correctness.
String Backtracking
Problems involving backtracking on strings.
01Letter Combinations of a Phone NumberMedium
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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
- Input: digits = "23"
- Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
def letterCombinations(self, digits: str) -> List[str]:
keyPad = ["", "", "abc", "def", "ghi", "jkl", "mno", "qprs", "tuv", "wxyz"]
res = []
curr = []
n = len(digits)
def backtrack(i):
if i == n:
res.append(''.join(curr))
else:
for c in keyPad[int(digits[i])]:
curr.append(c)
backtrack(i+1)
curr.pop()
backtrack(0)
return res if len(digits) > 0 else []O(4^n)O(n)We apply the template. We need to construct a map from digit -> list of possible characters.
These represent our choices at some digit i, we can map to any of these characters.
Note: there is an edge case at the end: if digits = "", backtrack(0) returns [""] instead of [], so we need the last check.
02Palindrome PartitioningMedium
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Example:
- Input: s = "aab"
- Output: [["a","a","b"],["aa","b"]]
def partition(self, s: str) -> List[List[str]]:
res = []
curr = []
n = len(s)
def backtrack(i):
if i == n:
res.append(curr.copy())
return
for j in range(i, n):
segment = s[i:j+1]
if segment == segment[::-1]:
curr.append(segment)
backtrack(j+1)
curr.pop()
backtrack(0)
return resO(n*2^n)O(n*2^n)Same idea. Our choices are substrings from i to j instead of single instances of j now. We try all substrings that start at index i, and if it's palindromic we backtrack.
Grid Backtracking
Problems involving backtracking on 2D grids.
01Sequential Grid Path CoverHard
You are given a 2D array grid of size m x n, and an integer k. There are k cells in grid containing the values from 1 to k exactly once, and the rest of the cells have a value 0.
You can start at any cell, and move from a cell to its neighbors (up, down, left, or right). You must find a path in grid which:
- Visits each cell in grid exactly once.
- Visits the cells with values from 1 to k in order.
Return a 2D array result of size (m * n) x 2, where result[i] = [xi, yi] represents the ith cell visited in the path. If there are multiple such paths, you may return any one.
If no such path exists, return an empty array.
def findPath(self, grid: List[List[int]], k: int) -> List[List[int]]:
dirs = [(0,1),(1,0),(-1,0), (0,-1)]
m, n = len(grid), len(grid[0])
def isInBounds(i, j):
return 0 <= i < m and 0 <= j < n
for i in range(m):
for j in range(n):
curr = []
res = None
# prev represents the latest non-zero value on the path up to
# and including the current (i,j) (or 0 if there were no no-zero values)
def backtrack(i, j, visited, prev):
nonlocal curr, res
if res: return
if (i, j) in visited: return
visited.add((i, j))
if len(curr) == m*n-1:
res = curr.copy() + [[i, j]]
return
for x, y in dirs:
ii, jj = i+x, j+y
if isInBounds(ii, jj) and (grid[ii][jj] == 0 or grid[ii][jj] == prev+1):
curr.append([i, j])
backtrack(ii, jj, visited, prev+(grid[ii][jj] == prev+1))
curr.pop()
visited.discard((i, j)) # need this
backtrack(i, j, set(), grid[i][j])
if res: return res
return []O(m*n * (m*n)!)O(m*n)Note we can do something like 0010203000400. Ie. we can interrupt the ascending sequence with 0's. This is not clear from the problem statement.
Few things: notice how we can use a global res variable to terminate our backtracking, and indicate if it is a success or not. Also, if we maintain a visited set in our backtracking, we need to remember to pop it at the end of the function. Other than that, this is just the template. If the neighbour is 0 or the next number in the sequence, this is a valid neighbour and we backtrack on it. We need to maintain prev, and remember to not reset it to 0 because we can have 0's that interrupt the ascending sequence.
Summary
When constraints are small, and there exists no obvious, efficient solution - backtracking offers a straightforward template to a working solution. Even when there exists a clever solution, backtracking can be a starting point.
Key Patterns:
1. Subsets: Either take or don't take each element → O(2^n)
2. Permutations: Swap elements to generate all orderings → O(n!)
3. Combinations: Choose k elements from n → O(C(n,k))
4. Pruning: Cut branches early when they can't lead to valid solutions
5. Deduplication: Use sets or skip consecutive duplicates after sorting
Common Mistakes:
- Forgetting curr.copy() when appending to results (otherwise all references point to the same empty list)
- Using j+1 instead of i+1 in permutations (or vice versa in combinations)
- Not handling empty input edge cases
- Forgetting to pop from visited set in grid backtracking