图论

回溯【56-63】

46.全排列

class Solution:def permute(self, nums):result = []self.backtracking(nums, [], [False] * len(nums), result)return resultdef backtracking(self, nums, path, used, result):if len(path) == len(nums):result.append(path[:])returnfor i in range(len(nums)):if used[i]:continueused[i] = Truepath.append(nums[i])self.backtracking(nums, path, used, result)path.pop()used[i] = False

78.子集

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:res = []self.backtracking(nums, 0, [], res)return resdef backtracking(self, nums, startindex, path, res):res.append(path[:])for i in range(startindex, len(nums)):path.append(nums[i])self.backtracking(nums, i+1, path, res)path.pop()

17.电话号码的字母组合

class Solution:def letterCombinations(self, digits: str) -> List[str]:self.mapping = {2:'abc', 3:'def', 4:'ghi', 5:'jkl',6:'mno',7:'pqrs',8:'tuv',9:'wxyz'}res = []if len(digits)==0:return resself.backtracking(digits, 0, [],res)return resdef backtracking(self, digits, startindex, path, res):    if len(path) == len(digits):res.append(''.join(path))  #将结果转换成strreturn #树宽是mapping[index],树高是len(digits)ss = self.mapping[int(digits[startindex])]for i in ss:path.append(i)self.backtracking(digits,startindex+1,path,res)path.pop()

39.组合总和

candidate元素不重复，一个元素可以重复选取

'''控制重复选取'''
self.backtracking(candidates, i, path, res, target)

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:res = []self.backtracking(candidates, 0, [],res,target)return resdef backtracking(self, candidates, startindex, path, res, target):if target == 0:res.append(path[:])return if target < 0:return for i in range(startindex, len(candidates)):path.append(candidates[i])target -=  candidates[i]self.backtracking(candidates, i, path, res, target)path.pop()target += candidates[i]

22.括号生成

什么时候可以向下搜索：

1. 插入数量 < n
2. 左括号插入数量 > 右括号数量

class Solution:def generateParenthesis(self, n: int) -> List[str]:res = []self.backtracking(n, 0, 0, '', res)return resdef backtracking(self, n, left, right, path, res):if left == n and right == n:res.append(path)returnif left<n:self.backtracking(n, left+1, right, path+'(', res )if left > right :self.backtracking(n, left, right+1, path+')', res)

79.单词搜索

递归参数
当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
：
终止条件

1. 返回 false ： (1) 行或列索引越界 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过
2. 返回 true ： k = len(word) - 1 ，即字符串 word 已全部匹配。

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:def dfs(i, j, k):if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return Falseif k == len(word) - 1: return Trueboard[i][j] = ''   #代表当前元素已经访问过，防止反复访问res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)board[i][j] = word[k]return res#遍历i，j，找到word[0]for i in range(len(board)):for j in range(len(board[0])):if dfs(i, j, 0): #当前在board[i][j],单词在word[k]return Truereturn False

131.分割回文串

class Solution:def partition(self, s: str) -> List[List[str]]:res =[]self.backtracking(s, 0, [], res)return resdef backtracking(self, s, startindex, path, res):if startindex == len(s):res.append(path[:])returnfor i in range(startindex, len(s)):ss = s[startindex:i+1]if ss == ss[::-1]:   #是回文， 再递归path.append(ss)self.backtracking(s, i+1, path, res )path.pop()

51. N 皇后

棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:result = []  # 存储最终结果的二维字符串数组chessboard = ['.' * n for _ in range(n)]  # 初始化棋盘self.backtracking(n, 0, chessboard, result)  # 回溯求解return [[''.join(row) for row in solution] for solution in result]  # 返回结果集def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None:if row == n:result.append(chessboard[:])  # 棋盘填满，将当前解加入结果集returnfor col in range(n):if self.isValid(row, col, chessboard):chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]  # 放置皇后self.backtracking(n, row + 1, chessboard, result)  # 递归到下一行chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]  # 回溯，撤销当前位置的皇后def isValid(self, row: int, col: int, chessboard: List[str]) -> bool:# 检查列for i in range(row):if chessboard[i][col] == 'Q':return False  # 当前列已经存在皇后，不合法# 检查 45 度角是否有皇后i, j = row - 1, col - 1while i >= 0 and j >= 0:if chessboard[i][j] == 'Q':return False  # 左上方向已经存在皇后，不合法i -= 1j -= 1# 检查 135 度角是否有皇后i, j = row - 1, col + 1while i >= 0 and j < len(chessboard):if chessboard[i][j] == 'Q':return False  # 右上方向已经存在皇后，不合法i -= 1j += 1return True  # 当前位置合法