回溯算法--python

一、回溯算法概述

回溯算法是一种通过穷举来解决问题的方法，它的核心是从一个初始状态出发，暴力搜索所有可能的解决方案，记录正确的解，知道找到解或者尝试了所有可能都找不到解为止。

常见的回溯算法有"深度优先搜索"，遍历整个空间，找到所有可能的节点，直到找到目标节点为止。

def pre_order(root):# 退出条件if root is None:return# 找到目标值后记录if root.val == '目标值':res.append(root)# 搜索全部可能的解决方案pre_order(root.left)pre_order(root.right)

回溯算法最重要的就是恢复本次尝试之前的状态，我们可以用列表的append和pop来实现将状态尝试和回退，只需要在上述代码加上两行代码即可。

def pre_order(root):# 退出条件if root is None:return# 尝试path.append(root)# 找到目标值后记录if root.val == '目标值':res.append(root)# 搜索全部可能的解决方案pre_order(root.left)pre_order(root.right)# 回退path.pop()

不过在很多问题上可能会有不止一个限制条件，而回溯本质上是对全局进行一个遍历，如果本身都不符合条件，则没有继续遍历的必要，节省大量的资源。

def pre_order(root):# 退出条件if root is None or root.val == '条件':return# 尝试path.append(root)# 找到目标值后记录if root.val == '目标值':res.append(root)# 搜索全部可能的解决方案pre_order(root.left)pre_order(root.right)# 回退path.pop()

二、全排列问题

1、不包含重复元素

力扣第46题：https://leetcode.cn/problems/permutations/description/

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

此类问题就是需要我们去获得全部的结果，通过不断的尝试和回退去获取所有可能的结果。本题因为是指定列表要构成的所有情况，所以最后生成的结果中，没有重复的元素，保证顺序不同，只需要递归给定数组长度次就可以得到所有的情况。

class Solution:def permute(self, nums: list[int]) -> list[list[int]]:# 获得给定列表长度lenth = len(nums)# 定义结果变量res = []# 定义回溯函数def get_back(count = 0):# 设定条件，如果递归次数达到给定数组长度次就将得到的结果记录下来if count == lenth:res.append(nums[:])return# 遍历所有元素for i in range(count, lenth):# 维护数组nums[count], nums[i] = nums[i], nums[count]# 增加迭代次数再次迭代get_back(count + 1)# 撤销操作nums[count], nums[i] = nums[i], nums[count]# 调用函数get_back()# 返回值return res

2、包含重复元素

力扣第47题：https://leetcode.cn/problems/permutations-ii/

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

该问题是上述问题的升级版本，该问题会出现重复的情况，此时我们就需要通过增加条件去对他进行剪枝，筛去重复(已经排序过的元素组合)，从而达到目标的条件。

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:# 获取给定列表的长度lenth = len(nums)# 定义结果变量res = []# 定义中间记录列表tmp_num = [0] * lenth# 定义判断是否重复列表judges = [False] * lenth# 定义迭代函数def get_back(count = 0):# 如果迭代次数达到目标值if count == lenth:# 就把目标排列加入的结果res.append(tmp_num[:])return# 遍历所有元素for i, judge in enumerate(judges):# 如果没有出现过就往下，剪枝if not judge:# 中间过度列表记录元素值tmp_num[count] = nums[i]# 该值被选择judges[i] = True# 下次元素选择get_back(count + 1)# 该值被抛出，回到选择前状态，过渡列表不需要恢复，因为每次是覆盖的状态judges[i] = Falseget_back()return res

三、子集和问题

1、给定的集合 无重复元素 且 可以重复使用 的情况

力扣39题：https://leetcode.cn/problems/combination-sum/description/

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

此类问题与上面的区别在于，子集中的元素如果一样，就算顺序不同，也算是相同子集，比如{2,2,3}和{3,2,2}实际上是一个答案，所以我们需要在解决问题时，同时解决重复子集的问题。

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:# 定义记录中间符合条件的列表tmp_nums = []# 定义记录结果的列表res = []# 定义回溯函数，start是开始遍历索引，get_sum是临时列表和def get_back(start = 0, get_sum = 0):# 如果回溯元素和等于目标值if get_sum == target:# 就添加符合条件的临时列表到结果中res.append(tmp_nums[:])return# 遍历所有元素(注意：这里是从上次遍历的索引开始遍历，避免生成重复的子集，如果不更新前面遍历起始点，则会出现重复子集)for i in range(start, len(candidates)):# 如果加上当前的值超过目标值，则直接尝试下一个值if get_sum + candidates[i] > target:continue# 尝试将暂时符合条件的元素加入列表tmp_nums.append(candidates[i])# 以当前临时列表为基础，更新开始遍历的索引与记录和get_back(i, get_sum + candidates[i])# 回退，撤销当前选择，恢复到之前的状态tmp_nums.pop()# 执行函数get_back()return res

2、给定的集合 有重复元素 不可以重复使用 的情况

力扣40题：https://leetcode.cn/problems/combination-sum-ii/description/

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:# 对列表元素进行排序，方便后期操作，主要是为了让相同的元素放在一块candidates.sort()# 定义存储临时列表tmp_nums = []# 定义存储符合条件的列表res = []# 定义回溯函数def get_back(start = 0, get_sum = 0):# 符合条件的列表直接放入结果列表中if get_sum == target:res.append(tmp_nums[:])return# 遍历所有元素，从上次遍历后的后一个元素开始遍历，避免出现重复的子集for i in range(start, len(candidates)):# 因为已经排序过了，所以当前元素不符合条件的情况下，后续元素肯定也不符合条件if get_sum + candidates[i] > target:return'''跳过相同的元素比如candidates = [10,1,2,7,6,1,5,2,2,2], target = 8排序后为[1,1,2,2,2,2,5,6,7,10]当选择完1,1,2,2,2(前三个2)后，不能再次选择从第二个2开始重新回溯，这样会导致出现1,1,2,2,2(后三个2)虽然从程序上讲，因为索引不同，所以两个列表实际选择的值不同但是从输出角度看，这是两个完全相同的列表，所以需要跳过相同元素，避免出现重复'''if (i > start and candidates[i] == candidates[i - 1]):continue# 尝试将暂时符合条件的元素加入列表tmp_nums.append(candidates[i])print(tmp_nums)print(start)'''以当前临时列表为基础，更新开始遍历的索引与记录和，注意这里有一点与上题不同后续选择的元素索引需要是在当前元素的后一个，避免出现重复选择的情况'''get_back(i + 1, get_sum + candidates[i])# 回退，撤销当前选择，恢复到之前的状态tmp_nums.pop()# 执行函数get_back()return res

3、给定的集合 无重复元素 不可以重复使用 的情况

力扣216题：https://leetcode.cn/problems/combination-sum-iii/description/

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

def combinationSum3(k: int, n: int) -> list[list[int]]:# 自己定义选取列表candidates = list(range(1, 10))# 定义存储临时列表tmp_nums = []# 定义存储结果列表res = []# 定义回溯函数def get_back(start=0, get_sum=0):# 如果选取值的和与目标值相等且长度相等，就加入到结果列表if get_sum == n and len(tmp_nums) == k:res.append(tmp_nums[:])return# 如果没有达到上面的条件，但是长度已经等于目标长度，直接返回if len(tmp_nums) == k:return# 遍历目标列表，因为不能有重复，所以要从上次迭代的下一个元素开始遍历for i in range(start, len(candidates)):# 尝试tmp_nums.append(candidates[i])# 继续递归，为了防止重复，起始位置设置为下一个get_back(i + 1, get_sum + candidates[i])# 回退tmp_nums.pop()# 调用get_back()return res

4、给定的集合 无重复元素 可以重复使用 顺序不同视为不同子集 的情况

力扣377题：https://leetcode.cn/problems/combination-sum-iv/description/

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

def combinationSum4(nums: list[int], target: int) -> int:# 定义存储临时列表tmp_nums = []# 定义存储符合的个数res = 0# 定义回溯函数def get_back(get_sum = 0):# 元素和与目标值相等，符合条件就计数+1if get_sum == target:# 闭包nonlocal，与global功能类似，使得内层函数可以使用外层函数变量nonlocal resres += 1return# 遍历所有元素，因为此时顺序不同视为不同子集，所以直接全部从开头遍历for i in range(len(nums)):# 剪枝if get_sum + nums[i] > target:continue# 尝试tmp_nums.append(nums[i])# 继续递归get_back(get_sum + nums[i])# 回退tmp_nums.pop()# 调用函数get_back()return res

不过该题用回溯会超时，建议使用动态规划^_

四、N皇后问题

力扣51题：https://leetcode.cn/problems/n-queens/description/

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

思路：创建一个空棋盘，定义同一列或同一斜线的布尔列表，判断是否有皇后存在。列上的比较好判断，只需要确定是否在同一个列索引就行，但是斜线较难判断，需要用一些数学思维。我们将左上角定义为原点，越往下下标越大，越往右下标越大，可以发现主对角线(从左上到右下)遵循一条规律：在同一条主对角线上的点，行与列的差值相等；次对角线(从右上到左下)遵循一条规律：在同一条次对角线上的点，行与列的和相等。借助这两条规律我们可以知道哪些位置与当前位置相关联。

def solveNQueens(n: int) -> list[list[str]]:# 创建棋盘state = [['.' for _ in range(n)] for _ in range(n)]# 判断当前列是否有皇后cols = [False] * n# 判断主对角线上是否有皇后diags1 = [False] * (2 * n - 1)# 判断次对角线上是否有皇后diags2 = [False] * (2 * n - 1)# 定义结果res = []def get_back(row = 0):# 所有的行放置完，记录答案if row == n:'''按照题目的意思内部组成字符串[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]'''res.append([''.join(row) for row in state])'''按照原本设计内部为列表[[['.', 'Q', '.', '.'], ['.', '.', '.', 'Q'], ['Q', '.', '.', '.'], ['.', '.', 'Q', '.']], [['.', '.', 'Q', '.'], ['Q', '.', '.', '.'], ['.', '.', '.', 'Q'], ['.', 'Q', '.', '.']]]'''# res.append([list(row) for row in state])return# 遍历所有的列for col in range(n):# 主对角线的列与行的坐标差值相同diag1 = row - col + n - 1# 次对角线的列与行的坐标和值相同diag2 = row + col# 判断对应的列、主对角线、次对角线上是否为True(True说明有皇后)if not cols[col] and not diags1[diag1] and not diags2[diag2]:# 没有就将目标坐标改为Qstate[row][col] = 'Q'# 对应的列、主对角线、次对角线改为True，说明该对应位置上有皇后了cols[col] = diags1[diag1] = diags2[diag2] = True# 继续遍历get_back(row + 1)# 回退状态，将放上去的皇后撤回state[row][col] = '.'# 对应的列、主对角线、次对角线改为False，说明该对应位置上的皇后撤销了cols[col] = diags1[diag1] = diags2[diag2] = False# 执行函数，开始回溯get_back()return res