Summary of Recursion.
LeetCode 77 Combinations
n is the width of the recursion tree. k is the depth of the recursion tree.
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
path = []
def backtrack(n, k, start):
if len(path) == k:
res.append(path[:])
return
for i in range(start, n + 1):
path.append(i)
backtrack(n, k, i+1)
path.pop()
backtrack(n, k, 1)
return res
Prune the tree: any recursion starting from the second element in current tree level is meaningless. len(path) is the number of element in the list at the current stage. k-len(path) is the number of additional elements we need. k-len(path)+1 is the starting point of recursion, at most. So to prune the tree, we end for loop at k-len(path)+1.
The time complexity is O(k* (n choose k)). It takes O((n choose k)) to enumerate combinations. And it takes O(k) to store each combination.
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
path = []
def backtrack(n, k, start):
if len(path) == k:
res.append(path[:])
return
for i in range(start, n-(k-len(path))+1 +1):
path.append(i)
backtrack(n, k, i+1)
path.pop()
backtrack(n, k, 1)
return res
LeetCode 17 Letter Combinations of a Phone Number
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
res = []
path = ""
MAP = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
if not digits: return []
def backtrack(digits, index, path):
if len(digits) == len(path):
res.append(path[:])
return
digit = int(digits[index])
letters = MAP[digit]
for i in range(len(letters)):
path += letters[i]
backtrack(digits, index+1, path)
path = path[:-1]
backtrack(digits, 0, path)
return res
LeetCode 39 Combination Sum
Note that same number can be repeatedly chosen.
For the vertical iteration, the stop criteria of recursion is 1) sum equals to the target 2) sum is larger than the target. For the horizontal iteration, in the first layer, we have n choices, from the first number to the last number, so the number of branches is n. In the first branch, we can only select number from n numbers (starting from the first number). In the second branch, we can only select number from n-1 numbers (starting from the second number). Note that we can select the same number. This pattern stays the same for other layers until the stoping criteria is satisfied.
Time complexity (loose): O(n*2^n). For n positions of the result, we choose or not choose a value. The space complexity is O(target), depending on the depth the recursion tree.
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
path = []
SUM = 0
def backtrack(candidates, target, SUM, start):
if sum(path) > target:
return
if sum(path) == target:
res.append(path[:])
return
for i in range(start, len(candidates)):
SUM += candidates[i]
path.append(candidates[i])
backtrack(candidates, target, SUM, i)
SUM -= candidates[i]
path.pop()
backtrack(candidates, target, SUM, 0)
return res
There are two optimizations: 1] when we determine whether sum > target , we already go into the next round of recursion. However, we don’t need to go to the next round of recursion if we determine sum + candidate[i] > target in advance. To implement this optimization, we add one line of code to return the back track function before going into the next round. 2] Notice that if we implement (1), we have to make sure that the candidate lists is sorted, because when we stop the next recursion, we are ignoring all the values after that node.
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
path = []
SUM = 0
def backtrack(candidates, target, SUM, start):
if sum(path) == target:
return res.append(path[:])
for i in range(start, len(candidates)):
if SUM + candidates[i] > target:
return
SUM += candidates[i]
path.append(candidates[i])
backtrack(candidates, target, SUM, i) # number can repeat
SUM -= candidates[i]
path.pop()
candidates = sorted(candidates)
backtrack(candidates, target, SUM, 0)
return res
LeetCode 40 Combination Sum II
Note that each number in the candidates list can only be used once in the combination, and there could be duplicates in the candidates list. The difficulty is that there are duplicates in the list but we cannot have duplicated combinations in the result. So the key is that we remove duplicates in the same layer, and do not remove duplicates in the same branch.
Time complexity (loose): O(n*2^n). N is the length of candidates. We need O(n) time to store each combination. There are O(2^n) number of combinations.
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
path = []
SUM = 0
def backtrack(candidates, target, SUM, start):
if sum(path) == target:
return res.append(path[:])
for i in range(start, len(candidates)):
if SUM + candidates[i] > target: return
if i > start and candidates[i] == candidates[i-1]: continue
SUM += candidates[i]
path.append(candidates[i])
backtrack(candidates, target, SUM, i+1) # same number cannot be used twice
SUM -= candidates[i]
path.pop()
candidates = sorted(candidates)
backtrack(candidates, target, SUM, 0)
return res
LeetCode 216 Combination Sum III
We are going to find all combinations of length k that sum up to the target number n. The time complexity is O(k* (n choose k)).
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
path = []
def backtrack(n, k, start):
if len(path) == k:
if sum(path) == n:
res.append(path[:])
return
for i in range(start, 9-(k-len(path))+2):
path.append(i)
backtrack(n, k, i+1)
path.pop()
backtrack(n, k, 1)
return res
LeetCode 131 Palindrome Partitioning
class Solution:
def partition(self, s: str) -> List[List[str]]:
res = []
path = []
def backtrack(s, start):
if start >= len(s):
res.append(path[:])
return
for i in range(start, len(s)):
temp = s[start:i+1]
if temp == temp[::-1]:
path.append(temp)
backtrack(s, i+1)
path.pop()
else:
continue
backtrack(s, 0)
return res
class Solution:
def partition(self, s: str) -> List[List[str]]:
res = []
path = []
def backtrack(s, start):
if start >= len(s):
res.append(path[:])
return
for i in range(start, len(s)):
if self.isPalindrome(s, start, i):
path.append(s[start:i+1])
backtrack(s, i+1)
path.pop()
else:
continue
backtrack(s, 0)
return res
def isPalindrome(self, s, start, end):
while start < end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
LeetCode 93 Restore IP Addresses
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
if len(s) > 12:
return res
def backtrack(s, start, point_num):
if point_num == 3:
if self.isvalid(s, start, len(s)-1):
res.append(s[:])
return
for i in range(start, len(s)):
if self.isvalid(s, start, i):
s = s[:i+1]+"."+s[i+1:]
backtrack(s, i+2, point_num+1)
s = s[:i+1]+s[i+2:]
else:
return
backtrack(s, 0, 0)
return res
def isvalid(self, s, start, end):
if start > end:
return False
if s[start] == "0" and start != end:
return False
if not 0 <= int(s[start:end+1]) <= 255:
return False
return True
LeetCode 78 Combinations
We are going to store all nodes in the recursion tree rather than only the leaves. In the implementation, we collection path before stopping recursion, to make sure every node is collected into the result list.
The stopping criteria is when the length of the path is equal to the length of the candidate list. So we simply iterate the nums list by using for loop and no other stopping criteria needed within the for loop.
The time complexity is O(n*2^n). There are O(2^n) combinations of a list of length n. Thinking of every number in the list can be chosen or not be chosen. It takes O(n) time to generate each list.
The space complexity is O(n), which is the space taken by path.
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtrack(nums, start):
res.append(path[:])
if len(path) == len(nums): # start == len(nums)
return
for i in range(start, len(nums)):
# no stopping criteria
path.append(nums[i])
backtrack(nums, i+1)
path.pop()
backtrack(nums, 0)
return res
LeetCode 90 Subsets II
There could be duplicates in the input list, but we do not want duplicated combinations in the result list. In the same level of the recursion tree, that is the for loop in the recursion function, we need to skip the duplicates. That also requires us to sort the input list in advance so as to easily determine duplicates.
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtrack(nums, start):
res.append(path[:])
if len(path) == len(nums):
return
for i in range(start, len(nums)):
# stopping criteria
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(nums, i+1)
path.pop()
nums = sorted(nums)
backtrack(nums, 0)
return res
LeetCode 46 Permutations
The difference between permutations and combinations is that the order matters for permutations. So we need to keep track of the number used in each recursion.
The assumption of using used list or checking whether the current number exists in the path, is that there is no duplicates in the input list.
Time complexity O(n * n!). The number of calling backtrack function is O(n!). It takes O(n) time to store the path result to the result list. The space complexity is O(n).
# Using `used`.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
used = []
path = []
def backtrack(nums, used):
if len(nums) == len(path):
return res.append(path[:])
for i in range(len(nums)):
if nums[i] in used:
continue
used.append(nums[i])
path.append(nums[i])
backtrack(nums, used)
used.pop()
path.pop()
backtrack(nums, used)
return res
# Not using `used`.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtrack(nums):
if len(nums) == len(path):
return res.append(path[:])
for i in range(len(nums)):
if nums[i] in path:
continue
path.append(nums[i])
backtrack(nums)
path.pop()
backtrack(nums)
return res
LeetCode 47 Permutation II
The additional condition based on LC 46 is that: there could be duplicated numbers. So we need to prune the tree when it leads to duplicated results. We only need to remove duplicates in the for loop. We don’t want to remove duplicates in the recursion rounds. So we do the following two things:
1 We keep track of which number is actually used by used array and skip it in the recursion, so that we make sure we are not repeatedly using any number.
2 In each layer of the recursion tree, we remove duplicates. In the implementation, within for loop, we check duplicate and skip it. Notice that all of the numbers considered in the same layer are not used.
Time complexity O(n * n!). The number of calling backtrack function is O(n!). It takes O(n) time to store the path result to the result list. The space complexity is O(n).
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
used = [0]*len(nums)
def backtrack(nums, used):
if len(nums) == len(path):
res.append(path[:])
return
for i in range(len(nums)):
if not used[i]:
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = 1
path.append(nums[i])
backtrack(nums, used)
path.pop()
used[i] = 0
nums = sorted(nums)
backtrack(nums, used)
return res
LeetCode 37 Sudoku Solver
LeetCode 51 N-Queens
We use a recursion tree to decide where to put the queen for each row. The depth and the width of the tree are O(n). The stopping criteria is 1) queens in the same row, 2) queens in the same column, 3) queens in the same diagonal line.
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
if not n: return []
board = [['.']*n for _ in range(n)]
res = []
def isValid(board, row, col):
# check col
for i in range(n):
if board[i][col] == 'Q':
return False
# check upper left
i = row-1
j = col-1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# check upper right
i = row-1
j = col+1
while i >=0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(board, row, n):
if row == n:
tmp_res = []
for tmp in board:
tmp_res.append("".join(tmp))
res.append(tmp_res)
return
for col in range(n):
if not isValid(board, row, col):
continue
board[row][col] = "Q"
backtrack(board, row+1, n)
board[row][col] = "."
backtrack(board, 0, n)
return res
LeetCode 491 Increasing Subsequences
Notice that we need to find all increasing subsequences rather than sort the array and generate all subsequences. In the recursion tree, the depth of the tree is the length of the input list. The stopping criteria is 1) when the length of the path is equal to the length of the input list, 2) when the new number added is larger than the final number in the path.
In the same level of the recursion tree under the same node, we skip the duplicated node, otherwise we would have duplicated combinations. A set used is used here to skip any number that is used. It is unique for each tree layer. Note that we cannot use used = [0] * len(nums) (see LeetCode 47) because we cannot sort the input list in advance. We are not using used to keep track of used numbers in recursion rounds, instead, we use start index to skip duplicated usage in recursion rounds. This is also different from LeetCode 47, where used is used to skip duplicates in both horizontal and vertical direction of the recursion tree.
The time complexity is O(2^n * n). The time complexity for enumerating all combinations is O(2^n). The space complexity is O(2^n).
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtrack(nums, start):
if len(path) >= 2: # store all combinations of length > 2
res.append(path[:])
if len(path) == len(nums):
return
used = set() # unique for each tree layer
for i in range(start, len(nums)):
if (path and nums[i] < path[-1]) or nums[i] in used:
continue
used.add(nums[i])
path.append(nums[i])
backtrack(nums, i+1)
path.pop()
backtrack(nums, 0)
return res
LeetCode 332 Reconstruct Itinerary
We can construct a recursion tree to decide which airport to arrive at. The stopping criteria is that the number of airport visited is equal to the number of tickets+1. The result of the path starting from the root to the leaf. Note that we don’t need to find all of the path. If we find one of them, we can immediately terminate the recursion.
All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”.
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
tickets_dict = defaultdict(list)
for item in tickets:
tickets_dict[item[0]].append(item[1])
path = ["JFK"]
def backtrack(start):
if len(tickets)+1 == len(path):
return True
tickets_dict[start].sort()
for _ in tickets_dict[start]:
end = tickets_dict[start].pop(0)
path.append(end)
if backtrack(end): # terminate if find one.
return True
tickets_dict[start].append(end)
path.pop()
backtrack('JFK')
return path
