目录

93. 复原 IP 地址

78. 子集 子集问题

90. 子集 II

491. 非递减子序列

46. 全排列 排列问题

47. 全排列 II

332. 重新安排行程 利用字典实现图

51. N 皇后 多维问题入门

37. 解数独 

---

 

93. 复原 IP 地址

要点：

本质上和上一期的回文字串切分是相似的，题意已经明确，每个字段都需要满足0到255的要求，因此，将要求作为一次递归的终止条件即可。

解法：

输入输出：

1. 原始数组；

2. startindex：用于指示当前的切割位置，避免重复分割

3. path：IP地址每个字段组成的路径

4. results：总结果

终止条件：

首先判断当前path中是否已经有三个元素，如果最后一个字段也符合要求，那么就可以终止并返回结果了

单步逻辑：

从startindex开始切分若干个结果，结果的要求需要符合题意，不能以0开始，且数值不能大于255。这是递归的单层逻辑。

实现：

class Solution:## 根据规则预定义一个判断函数 判断每段截取的字段是否合规def is_valid(self, s, start, end):if start > end:return False# 0开头且长度大于1的数字不合法if s[start] == '0' and start != end:  return Falsenum = int(s[start:end+1])return 0 <= num <= 255def backtrack(self, s, start_idx, path, results):## 判断数组长度和start_idx指向的位置决定是否返回if len(path) == 4 and start_idx == len(s):results.append('.'.join(path))returnelif len(path) > 4:return## 指定i的边界 防止最后一位索引出界for i in range(start_idx, min(start_idx + 3, len(s))):if self.is_valid(s, start_idx, i):part_str = s[start_idx: i + 1]path.append(part_str)self.backtrack(s, i + 1, path, results)path.pop()def restoreIpAddresses(self, s: str) -> List[str]:results = list() self.backtrack(s, 0, [], results)return results

78. 子集

 要点 子集问题：

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

其实子集也是一种组合问题，因为它的集合是无序的。由于无序，所以写算法时依然需要一个start_index来控制取样不重复。

相对地，求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和 {2, 1}是两个集合。

求所有节点的运算逻辑如下： 

 解法：

输入输出：

1. 输入数组；2. 起始索引；3. 路径；4. 所有结果

终止条件：

可以不设置终止条件

单步逻辑：

求取子集问题，不需要任何剪枝。因为子集就是要遍历整棵树。在每一个递归逻辑中搜集集合。

 实现：

class Solution:def backtrack(self, nums, start_idx, path, result):## 每个递归之前将当前path的子集结果输入result.append(path[:])for i in range(start_idx, len(nums)):path.append(nums[i])## 根据i确定后续横向遍历起始位置self.backtrack(nums, i + 1, path, result)path.pop()def subsets(self, nums: List[int]) -> List[List[int]]:result = list()self.backtrack(nums, 0, [], result)return result

90. 子集 II

要点：

回溯算法中的去重问题，在40.组合总和II (opens new window)中已经详细讲解过了，和本题是一个套路。后面的排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要。

回顾一下去重思路，首先需要对数组进行一个排序，使用used数组作为一个标记来记录前一个元素是否已经经过了遍历。随后，在横向遍历过程中，如果当前索引下的used的上一位是0，且当前元素和上一位的元素相同，这就说明这里是在重复进行上一个元素的遍历，跳过即可。

解法：

和组合去重十分相似，重要的是注意提前排序，否则会出现重复。

结果记录逻辑遵循幂集返回全部的规则，因此无需添加额外终止条件。

实现：

class Solution:def backtrack(self, nums, used, start_idx, path, results):results.append(path[:])for i in range(start_idx, len(nums)):if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == 0:continuepath.append(nums[i])used[i] = 1self.backtrack(nums, used, i + 1, path, results)used[i] = 0path.pop()def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:nums = sorted(nums)path, results = list(), list()used = [0] * len(nums)self.backtrack(nums, used, 0, path, results)return results

491. 非递减子序列

要点：

这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。这里要求去重，但是由于题目本身的限制，我们不能对输入数组进行排序。因此要换一种去重逻辑

 可以看到这里使用了一个树层去重的方案，在同一树层中，如果当前取的元素已经有数值相同的元素被取过了，那么就要去重了。

解法：

输入输出：1.输入数组；2.起始索引；3.当前路径；4.最终结果

终止条件：当索引位置到达最后一个元素时终止程序

单步逻辑：for循环遍历起始索引到len(nums)的元素，使用一个集合判断在每一个树层中没有重复使用的元素

实现：

class Solution:def backtrack(self, nums, start_idx, path, results):if len(path) > 1:results.append(path[:])used = set()for i in range(start_idx, len(nums)):if (nums[i] in used) or (len(path) > 0 and nums[i] < path[-1]):continueused.add(nums[i])path.append(nums[i])self.backtrack(nums, i + 1, path, results)path.pop()def findSubsequences(self, nums: List[int]) -> List[List[int]]:path, results = list(), list()self.backtrack(nums, 0, path, results)return results

46. 全排列

 要点：

排列问题不需要使用startIndex了，因为取元素时会遇到无序的情况。但排列问题需要一个used数组，标记已经选择的元素，这样才可以保证取元素时的正确性。

解法：

输入输出：1.输入数组；2.used数组记录元素使用情况；3.当前路径path；4.最终结果results

单步逻辑：使用used判断当前索引是否已经被使用，被使用则跳过

终止条件：收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

实现：

class Solution:def backtrack(self, nums, used, path, results):if len(path) == len(nums):results.append(path[:])for i in range(len(nums)):if used[i]:continueused[i] = Truepath.append(nums[i])self.backtrack(nums, used, path, results)path.pop()used[i] = Falsedef permute(self, nums: List[int]) -> List[List[int]]:used = [False] * len(nums)path, results = list(), list()self.backtrack(nums, used, path, results)return results

47. 全排列 II

要点：

这道题目和46.全排列 (opens new window)的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。这里又涉及到去重了。数组的去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

解法：

输入输出：加入一个used来对树层上的重复使用进行判断

终止条件：path的长度等于输入数组的长度时终止

单步逻辑：普通排列检查当前数值是否已经被使用，这里要转换成同树层前一位是否被读取了

实现：

class Solution:def backtrack(self, nums, used, path, results):if len(path) == len(nums):results.append(path[:])for i in range(len(nums)):## 通过两个条件过滤掉两种可能的重复if (i > 0 and used[i - 1] == 0 and nums[i] == nums[i - 1]) or used[i] == 1:continuepath.append(nums[i])used[i] = 1self.backtrack(nums, used, path, results)used[i] = 0path.pop()def permuteUnique(self, nums: List[int]) -> List[List[int]]:nums = sorted(nums)used = [0] * len(nums)path, results = list(), list()self.backtrack(nums, used, path, results)return results

332. 重新安排行程

• JFK - 约翰·F·肯尼迪国际机场 (John F. Kennedy International Airport)，位于美国纽约。
• MUC - 慕尼黑机场 (Munich Airport)，位于德国慕尼黑。
• LHR - 伦敦希思罗机场 (London Heathrow Airport)，位于英国伦敦。
• SFO - 旧金山国际机场 (San Francisco International Airport)，位于美国旧金山。
• SJC - 圣荷西国际机场 (San Jose International Airport)，位于美国加利福尼亚州圣荷西。

要点：

本题是回溯法的一个拓展，这道题目有几个难点：

1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
2. 有多种解法，字母序靠前排在前面，如何该记录映射关系呢 ？
3. 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
4. 搜索的过程中，如何遍历一个机场所对应的所有机场。

1. 死循环：由案例2可以看到，部分情况下会持有往返机票，如果往返的行程字典序靠前，且没有处理好去重，那么就会陷入死循环。理解为一张机票只能用一次。

2. 映射关系：单个出发地会映射多个可及的目的地，这里需要使用字典进行处理

3. 回溯树形结构：

解法：

0. 外层准备：

将机票信息转换为图的邻接表，提前做好反序方便弹出调用，保证每张票只用一次

1. 输入输出：

假设想要找到符合排序的路径，可以以当前所在的机场作为输入，然后遍历当前出发点的所有可达目的地，按照排序来挑选符合要求的目的地。因此，回溯的输入包括：1.当前位置；2.机票信息（处理成字典方便按出发地查找）；3.最终结果。也可以记录一个path，不过既然只要取最优结果，就可以在回溯过程做好排列，确保每次加入的行程是最优的即可

2. 终止条件：

如果当前机场已经没有能去的目的地，就要终止了；由于测试例能够保证一定有解，因此可以不加入行程的长度判断，这表示

3. 单步逻辑：

使用pop弹出优先的目的地，题意保证了这条路线是可以探索到底的；

将目的地作为新的出发点继续遍历，出递归后输出结果。

实现：

class Solution:def backtrack(self, ticket_dict, department, results):while ticket_dict[department]:## 这里用字典的键中pop 因此需要提前做好反序 ## 这个行为可以保证每次先推出排序靠前的目的地 且每张机票只能用一次 ## 如果后续目的地都是合法的 那么就可以持续递归到最终结果terminal = ticket_dict[department].pop()self.backtrack(ticket_dict, terminal, results)## 这里将出发点记录在路径中 出回溯之后才会添加出发地## 因此添加顺序是反向的results.appendleft(department)def findItinerary(self, tickets: List[List[str]]) -> List[str]:from collections import defaultdict, deque## 将机票数据转化为一个图的邻接表 即字典 并按字典序逆序存储目的地ticket_dict = defaultdict(list)for ticket_info in tickets:ticket_dict[ticket_info[0]].append(ticket_info[1])# print(ticket_dict)for depart in ticket_dict:ticket_dict[depart].sort(reverse = True)# print(ticket_dict)## 用一个deque方便更清晰清晰描述算法逻辑results = deque()self.backtrack(ticket_dict, 'JFK', results)return list(results)

51. N 皇后

要点：

n个皇后放置在n*n的棋盘，根据题意可知，同一行不可能存在两个皇后。因此遍历的顺序就可以按行进行位置遍历，然后排除同列和斜线攻击的情况。这样就转换成了树形结构深度为n的嵌套循环的逻辑。收集所有情况就可以输出到结果。

解法：

输入输出：

1.传入当前棋盘（某节点），2.row_idx 和startidx类似，指定目前遍历的是第几行

这里的输出是将单个棋盘的情况转成了一维的字符串数组，实际上输出的构成是 棋盘*列*行的三维形式

单步逻辑：预定义一个函数来判断，输入一个坐标，它的行列斜线中（其实只需要检查上方，因为下方还没有填充）是否出现了其他皇后。如果合法，那么放入皇后，将放置过的结果带入下一轮回溯。

终止条件：放置完最后一个皇后输出。非法情况要在递归中过滤，防止重复处理

实现:

二维过程还是比较容易把列和行错位，最好把变量写清晰

class Solution:def is_valid(self, cb, row_idx, col_idx):# 同一列有皇后for row in cb:if row[col_idx] == 'Q':return False# 左上有皇后i, j = row_idx - 1, col_idx - 1while i >= 0 and j >= 0:if cb[i][j] == 'Q':return Falsei -= 1j -= 1# 右上有皇后i, j = row_idx - 1, col_idx + 1while i >= 0 and j < len(cb):if cb[i][j] == 'Q':return Falsei -= 1j += 1return Truedef put_queen(self, row, i):return row[:i] + 'Q' + row[i+1:]def pop_queen(self, row, i):return row[:i] + '.' + row[i+1:]def backtrack(self, n, chess_board, row_idx, results):if row_idx == n:results.append(chess_board[:])returnfor col_idx in range(n):if self.is_valid(chess_board, row_idx, col_idx):chess_board[row_idx] = self.put_queen(chess_board[row_idx], col_idx)self.backtrack(n, chess_board, row_idx + 1, results)chess_board[row_idx] = self.pop_queen(chess_board[row_idx], col_idx)def solveNQueens(self, n: int) -> List[List[str]]:chess_board = ['.' * n] * n results = list()self.backtrack(n, chess_board, 0, results)return results

37. 解数独 

要点：

N皇后问题 (opens new window)是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。

本题就不一样了，本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。

具体来说，N皇后问题只需要按行遍历即可，因为这是游戏规则决定的。但是数独每行都需要摆放多个数字；同时，还要满足3*3的小矩阵内没有重复。

因此这里是一个二维的回溯，比N皇后问题在外层多一层嵌套：一个for循环确定行，一个for循环确定列，然后进入递归，去判断这个格子应该放置哪个合法数字。

解法：

输入输出：1.输入当前棋盘，2.输入空格位置，3.根据棋盘判断能够填入的合法数字

终止条件：回溯使用bool值进行返回，一直填满终止

单步逻辑：1. 使用一个嵌套循环确定当前遍历位置，2. 判断当前位置是否已经有数字，如果还是空，则使用一个预定义函数来确定当前位置可以填入的数字，3. 移动到下一个位置，进行后续的遍历。

实现：

可以发现树形结构是比较有规律的，要点在于：1. 使用清晰有效的预定义函数来判断待填入数字；2. 回溯部分使用bool类型返回，可以快速锁定正确的路径，

下面先展示一下目前可以ac的解法，由于测试例做了修改，使用朴素的递归加每个格点逐个判断会导致超时，因此，这里额外借助一个储存空间，同时每次优先解决可用数字最少的格子，帮助我们减少暴力遍历整个大矩阵的次数：

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:#初始化数据结构 记录每一行 每一列、每个小矩阵中已经填入的数字·rows  = [set() for _ in range(9)]cols  = [set() for _ in range(9)]boxes = [set() for _ in range(9)]## 遍历一遍现有矩阵 存入已有的数字## 这里存入了9行 9列 和9个小矩阵for r in range(9):for c in range(9):if board[r][c] != '.': num = board[r][c]## 对每个行列小矩阵进行一次赋值rows[r].add(num)cols[c].add(num)## 例如 4行5列 得到 3+1 index为4的小矩阵box_index = (r//3)*3 + (c//3)boxes[box_index].add(num)#找到下一个待填充的空格 启发式搜索 def next_empty_cell():# 候选数字的数量最大是9个，初始化值大于最大可能值，避免边界问题min_options = 10 # 候选数字最少的单元格坐标best_cell = None for r in range(9):for c in range(9):## 如果是空白单元格 需要填数字if board[r][c] == '.':box_index = (r // 3) * 3 + c // 3possible_numbers = set('123456789') - rows[r] - cols[c] - boxes[box_index]## 寻找可用数字最少的格子if len(possible_numbers) < min_options:min_options = len(possible_numbers)best_cell = (r,c)if min_options == 1:return best_cellreturn best_celldef backtracking():# 先找到一个候选数字最少的空单元格cell = next_empty_cell()# 如果已经没有空单元格说明找到了解决方案if not cell:return True #计算候选数字r, c = cellbox_index = (r // 3) * 3 + c //3possible_numbers = set('123456789') - rows[r] - cols[c] - boxes[box_index]#尝试候选数字for num in possible_numbers:#更新棋盘和对应的数据结构board[r][c] = num rows[r].add(num)cols[c].add(num)boxes[box_index].add(num)if backtracking():return Trueboard[r][c] = '.'rows[r].remove(num)cols[c].remove(num)boxes[box_index].remove(num)return Falsebacktracking()

第一种解法先提取了可以使用的数字进行递归，在已出现数字较少的情况下会超时：

from typing import Listclass Solution:def valid_nums(self, row_idx, col_idx, board):## 查找本行已经使用过的数字row_num = set(int(num) for num in board[row_idx] if num != '.')## 查找本列已经使用过的数字col_num = set(int(board[i][col_idx]) for i in range(9) if board[i][col_idx] != '.')## 查找小矩阵中已经使用过的数字mat_row_start = (row_idx // 3) * 3mat_col_start = (col_idx // 3) * 3mat_num = set()for i in range(mat_row_start, mat_row_start + 3):for j in range(mat_col_start, mat_col_start + 3):if board[i][j] != '.':mat_num.add(int(board[i][j]))## 求矩阵并集exist_num_set = row_num | col_num | mat_num## 求剩余有效的可用数字valid_num_set = set(range(1, 10)).difference(exist_num_set)return valid_num_setdef back_track(self, board):for row_idx in range(9):for col_idx in range(9):# 对已填充的格子不做处理if board[row_idx][col_idx] != '.':continue# 提取可用数字valid_num_set = self.valid_nums(row_idx, col_idx, board)if not valid_num_set:return False# 对每个格子递归当前可用的数字for num in valid_num_set:board[row_idx][col_idx] = str(num)if self.back_track(board):return True# 清除当前数字以进行回溯board[row_idx][col_idx] = '.'  return False# 如果所有位置都填满，返回 Truereturn True  def solveSudoku(self, board: List[List[str]]) -> None:self.back_track(board)

直接对每个格子遍历1-9数字，不合法直接返回false来加速，仍然有一个测试例超时：

class Solution:def is_valid(self, row_idx, col_idx, board, n):## 排除行相同for num in board[row_idx]:if n == num:return False## 排除列相同for i in range(9):if n == board[i][col_idx]:return False## 排除小矩阵相同mat_row_start = (row_idx // 3) * 3mat_col_start = (col_idx // 3) * 3for i in range(mat_row_start, mat_row_start + 3):for j in range(mat_col_start, mat_col_start + 3):if n == board[i][j]:return Falsereturn Truedef back_track(self, board):for row_idx in range(9):for col_idx in range(9):# 对已填充的格子不做处理if board[row_idx][col_idx] != '.':continue# 对每个格子递归当前可用的数字for n in range(1, 10):if self.is_valid(row_idx, col_idx, board, str(n)):board[row_idx][col_idx] = str(n)if self.back_track(board):return Trueboard[row_idx][col_idx] = '.'  return False# 如果所有位置都填满，返回 Truereturn True  def solveSudoku(self, board: List[List[str]]) -> None:self.back_track(board)