Solution to LeetCode 332 Reconstruct Itinerary and LeetCode 491 Increasing Subsequences.
LeetCode 332
Reconstruct Itinerary (Hard) [link]
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
LeetCode 491
Increasing Subsequences (Medium) [link]
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
