Chapter 3: Backtracking:

Context:
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.
Template:
def f(self, s: str) -> List[List[int]]:
n = len(s)
res = []
curr = []
def backtrack(i):
if i == n:
[Link]([Link]()) # base case: this is valid so add to res
# NEED THIS [Link]()... 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
[Link](j) # append to curr
backtrack(j+1) # recurse on remaining
[Link]() # undo append to curr, try next choices for j

backtrack(0)
return res

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.

Problem 0: Subsets

Given a list of numbers, return a list of all subsets.

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Solution: 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.

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.

def subsets(self, nums: List[int]) -> List[List[int]]:

res = []
subset = []
def backtrack(i):
if i == len(nums):
[Link]([Link]())
else:
# use nums[i]
[Link](nums[i])
backtrack(i+1)
[Link]()

# do not use nums[i]

backtrack(i+1)

backtrack(0)
return res

Time: O(n*2^n). There are 2^n items in the final list, and each list can have up to n items.
Space: O(n*2^n)

Problem 1: Unique Subsets: 90. Subsets II

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.

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)
 def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = set()
subset = []
def backtrack(i):
if i == len(nums):
[Link](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]
[Link](nums[i])
backtrack(i+1)
[Link]()

# do not use nums[i]

backtrack(i+1)

backtrack(0)
return list(res)

We can also simply leverage the solution from Problem 0 Subsets. Just remove duplicates.

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

return list(set(tuple(sorted(A)) for A in subsets(nums)))

Same time and space as subsets.

Problem 2: Combinations:

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)

class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
 res = []
curr = []
def backtrack(i):
if len(curr) == k:
[Link]([Link]())
else:
for j in range(i, n+1):
[Link](j)
backtrack(j+1)
[Link]()

backtrack(1)
return res

O(n * {n choose k}) time and space.

Problem 3: Permutations:

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. 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.

class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []

# swap
def backtrack(i):
if i == n:
[Link]([Link]())
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 res
O(n*n!) time and space since there are n! Permutations. N choices for index 0, n-1 choices for
index 1, … 1 choice for index n-1.

Problem 4: Unique Permutations: Permutations 2:

You know the drill.

def permuteUnique(self, nums: List[int]) -> List[List[int]]:

n = len(nums)
res = set()

# swap
def backtrack(i):
if i == n:
[Link](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)

def permuteUnique(self, nums: List[int]) -> List[List[int]]:

return list(set(tuple(A) for A in permute(nums)))

Problem 5: Combination Sum

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.
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.

# 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:
[Link]([Link]())
else:
# try to take every element. recurse on rest
for j in range(i, n):
[Link](candidates[j])
curr_target -= candidates[j]

backtrack(j) # not j+1 !!! since we can re-use j

curr_target += candidates[j]
[Link]()
backtrack(0)
return res
Runtime: O(n* 2^n) time and space.

Problem 6: Combination Sum 2

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.

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.

def combinationSum2(self, candidates: List[int], target: int) ->

List[List[int]]:
res = []
curr = []
curr_target = target
n = len(candidates)
[Link]()

def backtrack(i):
nonlocal curr_target
if curr_target < 0: return
if curr_target == 0:
[Link]([Link]())
else:
for j in range(i, n):
[Link](candidates[j])
curr_target -= candidates[j]

backtrack(j+1)

curr_target += candidates[j]
 [Link]()

backtrack(0)
return list(set(tuple(A) for A in res)) # tle...

def combinationSum2(self, candidates: List[int], target: int) ->

List[List[int]]:
res = []
curr = []
curr_target = target
n = len(candidates)
[Link]() # need this to skip multiple same values in order...

def backtrack(i):
nonlocal curr_target
if curr_target < 0: return
if curr_target == 0:
[Link]([Link]())
else:
for j in range(i, n):
if j >= i+1 and candidates[j] == candidates[j-1]: continue
# NEED THIS... skip dups
[Link](candidates[j])
curr_target -= candidates[j]

backtrack(j+1)

curr_target += candidates[j]
[Link]()

backtrack(0)
return res

Combination Sum 3???

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.

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.

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:
[Link]([Link]())
else:
for j in range(i, 10):
if sum_ + j > n:
break
sum_ += j
[Link](j)

backtrack(j+1)

[Link]()
sum_ -= j

backtrack(1)

return res
Problem 7: Letter Combinations of a Phone Number

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.

Input: digits = "23"

Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

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.

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:
[Link](''.join(curr))
else:
for c in keyPad[int(digits[i])]:
[Link](c)
backtrack(i+1)
[Link]()

backtrack(0)
return res if len(digits) > 0 else []
Problem 8: 131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all
possible palindrome partitioning of s.
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

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.

def partition(self, s: str) -> List[List[str]]:

res = []
curr = []
n = len(s)

def backtrack(i):
if i == n:
[Link]([Link]())
return

for j in range(i, n):

segment = s[i:j+1]

if segment == segment[::-1]:
[Link](segment)

backtrack(j+1)

[Link]()

backtrack(0)

return res
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

3565. Sequential Grid Path Cover

You are given a 2D array grid of size m x n, and an integer k. There are k cells in gridcontaining 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

[Link]((i,j))

if len(curr) == m*n-1:

res = [Link]() + [[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):

[Link]([i,j])

backtrack(ii,jj, visited, prev+(grid[ii][jj] ==

prev+1))

[Link]()

[Link]((i,j)) # need this

backtrack(i,j,set(), grid[i][j])

if res: return res

return []

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.