学习链接：leetcode-notes/docs/ch04/04.03/04.03.01-Backtracking-Algorithm.md at main · datawhalechina/leetcode-notes · GitHub
全排列的回溯过程：
- 按顺序枚举每一位上可能出现的数字，之前已经出现的数字在接下来要选择的数字中不能再次出现。
- 对于每一位，进行如下几步：
- 选择元素：从可选元素列表中选择一个之前没有出现过的元素。
- 递归搜索：从选择的元素出发，一层层地递归搜索剩下位数，直到遇到边界条件时，不再向下搜索。
- 撤销选择：一层层地撤销之前选择的元素，转而进行另一个分支的搜索。直到完全遍历完所有可能的路径。
伪代码形式：
for i in range(index, len(nums)): # 枚举可选元素列表path.append(nums[i]) # 选择元素backtracking(nums, i + 1) # 递归搜索path.pop() # 撤销选择例题及思路：
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
第一步先把单词分成数组，然后把word[0]在网格中定位，然后用函数来判断是否能组成单词。如果不行，就到下一个地方值为word[0]开始判断。
第二步就是写这个判断的函数了，对四周进行判断，能不能找到word[1]，就是用回溯算法。
在回溯算法中，需要注意：
1、还需要标记已经访问过的位置，避免重复访问
2、处理边界情况，确保搜索不会超出网格范围
class Solution(object):def exist(self, board, word):""":type board: List[List[str]]:type word: str:rtype: bool"""rows = len(board) # 网格的行数cols = len(board[0]) # 网格的列数def find_first_letter():"""第一步是在网格中定位单词的首字母 word[0]，然后调用函数来判断从这个位置开始是否能组成单词。如果不能，就寻找下一个值为 word[0] 的位置进行判断。此函数用于在网格中查找单词的首字母，如果找到首字母且从该位置能组成单词则返回 True，否则返回 False"""for row in range(rows): # 遍历网格的每一行for col in range(cols): # 遍历网格的每一列if board[row][col] == word[0]: # 如果当前位置的字符等于单词的首字母visited = [[False for _ in range(cols)] for _ in range(rows)] # 初始化访问标记矩阵if self.check_surroundings(row, col, 0, visited): # 检查从该位置开始能否组成单词return True # 能组成则返回 Truereturn False # 遍历完都没找到能组成单词的首字母位置，返回 Falsedef check_surroundings(self, row, col, index, visited):"""第二步是编写这个判断的函数，运用回溯算法对四周进行判断能否找到 word 中对应索引位置的字符。在回溯算法中，需要注意：1. 标记已经访问过的位置，避免重复访问。2. 处理边界情况，确保搜索不会超出网格范围。此函数用于从给定的位置开始，检查能否通过周围的字符组成单词:param row: 当前行坐标:param col: 当前列坐标:param index: 单词中当前要匹配的字符索引:param visited: 标记矩阵，记录哪些位置已访问:return: 能组成单词返回 True，否则返回 False"""if row < 0 or row >= rows or col < 0 or col >= cols: # 处理边界情况return Falseif visited[row][col] or board[row][col]!= word[index]: # 已访问 or 字符不匹配return Falseif index == len(word) - 1: # 已匹配到单词的最后一个字符return Truevisited[row][col] = True # 标记当前位置已访问found = (self.check_surroundings(row - 1, col, index + 1, visited) or # 检查上方位置self.check_surroundings(row + 1, col, index + 1, visited) or # 检查下方位置self.check_surroundings(row, col - 1, index + 1, visited) or # 检查左方位置self.check_surroundings(row, col + 1, index + 1, visited)) # 检查右方位置visited[row][col] = False # 回溯，取消当前位置的访问标记return foundself.check_surroundings = check_surroundings.__get__(self, Solution) # 将函数绑定到类实例return find_first_letter() # 返回查找首字母的结果
