332.重新安排行程

思路：

1.确定回溯函数参数：定义全局遍历存放path，

2.终止条件：遍历完所有路径，机场个数，如果达到了（航班数量+1），即path的长度应当为字符串二维数组长度 + 1

3.遍历过程：每次取出某节点后，将这个节点从备用选择中删除，防止出现循环路径

class Solution:def findItinerary(self, tickets: List[List[str]]) -> List[str]:path = ["JFK"]# defaultdic(list) 是为了方便直接appendtickets_dict = defaultdict(list)for item in tickets:tickets_dict[item[0]].append(item[1])# 给每一个机场的到达机场排序，小的在前面，在回溯里首先被pop(0）出去# 这样最先找的的path就是排序最小的答案，直接返回for airport in tickets_dict: tickets_dict[airport].sort()# tickets_dict里面的内容是这样的# {'JFK': ['ATL', 'SFO'], 'SFO': ['ATL'], 'ATL': ['JFK', 'SFO']})def backtracking(start_point):# 终止条件if len(path) == len(tickets) + 1:return Truefor _ in tickets_dict[start_point]:#必须及时删除，避免出现死循环end_point = tickets_dict[start_point].pop(0)path.append(end_point)# 只要找到一个就可以返回了if backtracking(end_point):return Truepath.pop()tickets_dict[start_point].append(end_point)backtracking("JFK")return path

51.N皇后

思路：

1.确定回溯函数参数：定义全局遍历存放res，参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了

2.终止条件：当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。

3.遍历过程：

递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。

每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

• 枚举出当前行所有的列。对于每一列位置：

  • 约束条件：定义一个判断方法，先判断一下当前位置是否与之前棋盘上放置的皇后发生冲突，如果不发生冲突则继续放置，否则则继续向后遍历判断。

  • 选择元素：选择 row, col 位置放置皇后，将其棋盘对应位置设置为 Q。

  • 递归搜索：在该位置放置皇后的情况下，继续递归考虑下一行。

  • 撤销选择：将棋盘上 row, col 位置设置为 . 。

• 验证棋盘是否合法

  按照如下标准去重：

  1. 不能同行
  2. 不能同列
  3. 不能同斜线 （45度和135度角）

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:if not n: return []res = []chessboard = [['.'] * n for _ in range(n)]def isValid(row, col, chessboard):# 判断每列for i in range(len(chessboard)):if chessboard[i][col] == 'Q':return False# 判断左上角i = row - 1j = col - 1while i>=0 and j>=0:if chessboard[i][j] == 'Q':return Falsei -= 1j -= 1# 判断右上角i = row - 1j = col + 1while i>=0 and j<n:if chessboard[i][j] == 'Q':return Falsei -= 1j += 1return Truedef backtrack(n, row, chessboard):if row == n:temp_res = []for temp in chessboard:temp_str = "".join(temp)temp_res.append(temp_str)res.append(temp_res)for col in range(n):if not isValid(row, col, chessboard):continuechessboard[row][col] = 'Q'backtrack(n, row+1, chessboard)chessboard[row][col] = '.'backtrack(n, 0, chessboard)return res

37.解数独

思路:

1.确定回溯函数参数：递归函数的返回值需要是bool类型，为什么呢？

因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值

2.终止条件：本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。

3.遍历过程：

枚举出当前位置填的值：

• 约束条件：判断同行，同列，9宫格是否出现该值。

• 选择元素：对board中”.“位置，赋值k（1-9)

• 递归搜索：递归判断该取值是否可以

• 撤销选择：将该位置重置为”.“

判断棋盘是否合法有如下三个维度：

• 同行是否重复
• 同列是否重复
• 9宫格里是否重复

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""def isValid(row, col, k, board):# 判断同行for i in range(9):if board[row][i] == str(k):return False# 判断同列for j in range(9):if board[j][col] == str(k):return False# 判断同个九宫格  startrow = (row // 3) * 3startcol = (col // 3) * 3for i in range(startrow, startrow + 3):for j in range(startcol, startcol + 3):if board[i][j] == str(k):return  Falsereturn Truedef backtrack(board):for i in range(len(board)): # 遍历行for j in range(len(board[0])):  # 遍历列if board[i][j] != ".":continuefor k in range(1,10):if isValid(i, j, k, board):board[i][j] = str(k)if backtrack(board):return Trueboard[i][j] = "."return Falsereturn Truebacktrack(board)