回溯算法
力扣上典型的回溯算法相关题目如下：
| 序号 | 题目 |
|---|---|
| 1 | 332. 重新安排行程 |
应用
应用1：Leetcode.332
题目
分析
假设有 \(n\) 张机票，那么，就可以经过 \(n + 1\) 个机场，因此，回溯过程的终止条件，即路径上的点的个数比机票数多 \(1\) 个。
我们定义个递归函数：
def dfs(self, ticket_num: int, trips: dict[dict[int]], path: List[str]) -> bool:
利用后序遍历的思路，去判断从当前起点开始，能否经过所有的机场。
算法步骤：
-
先对所有的机票按照字典序排序；
-
用 \(hash\) 表 \(trips\) 记录每一对起点到终点的数量；
-
从起点开始，按照字典序回溯每一个目的机场最终能否经过所有的机场；
-
如果能到达所有的机场，则该路径满足条件；
-
如果不能到达所有的机场，则继续回溯。
-
代码实现
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
trips = defaultdict(dict)
# 先对tickets按照字典序排序，因为python中的dict是有序字典
tickets.sort(key = lambda x: (x[0], x[1]))
for _from, _to in tickets:
if _from not in trips:
trips[_from] = defaultdict(int)
trips[_from][_to] += 1
path = ["JFK"]
self.dfs(len(tickets), trips, path)
return path
def dfs(self, ticket_num: int, trips: dict[dict[int]], path: List[str]) -> bool:
if len(path) == ticket_num + 1:
return True
start = path[-1]
# 优先遍历字典序靠前的目的机场，如果满足条件则加入路径中
for destination, count in trips[start].items():
if trips[start][destination] < 1:
continue
path.append(destination)
trips[start][destination] -= 1
if self.dfs(ticket_num, trips, path):
return True
path.pop()
trips[start][destination] += 1
return False
参考：