算法秘籍之拿下回溯

回溯算法也称暴力解算法，这类问题分为几大类别，快速识别不同的回溯方法可以极大的帮助我们处理回溯问题，下面是根据本人最近刷的力扣回溯专题做的一个总结。

• 常规回溯
• 元素可重复选
• 元素不可重复选
• 排列问题(考虑顺序)
• 组合问题(不考虑顺序)
• 解存在问题

常规回溯
回溯算法也就是多叉树的深度遍历,有多少个选择就有多少层，下面是回溯算法的模板结构。

 def trace_back(与结束条件有关的参数(一般是层数，元素个数，字符串长度,可以无->则遍历路径上的所有值可作为解), 初始的求解参数(如果存在多个可以外部套for遍历初始值)):if 结束条件(也叫剪纸条件):收集结果(收集数组或字符串结果，收集bool结果可以 if trace_back():然后深度判断是否存在True)for _ in 可选择列表(结果树的分支数):trace_back()#撤销操作，撤销当前选择的元素de_trace_back

元素可重复
元素可重复选择:可以使用for循环每次回溯都可以选择所有元素
元素不可重复
元素不可重复选择:可以使用dict标记已经选过的元素，for循环中通过判断元素是否使用来决定回溯

# 初始每个元素都没有被选择所以都为False
uselist = [False]*n
def trace_back(n):if 结束条件：收集结果for x in 可选的元素列表：# 如果元素没有被选过则继续遍历if not uselist[x]:trace_back(x)de_trace_back()

排列问题
考虑顺序的选择:不同的选择顺序可以作为一个解，解法与不可重复类似确保每个元素都被选上且仅选择一次。

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:length = len(nums)uselist = [False] * lengthans = []tem = []def back_tracing(n):if n == length:ans.append(tem[:])for i in range(length):if not uselist[i]:uselist[i] = Truetem.append(nums[i])back_tracing(n + 1)uselist[i] = Falsetem.pop()back_tracing(0)return ans

组合问题
不考虑顺序的选择:相同元素不同顺序不作为新解，此时需要有回溯的方向，不可以走回头路。(列表的体现就是下标一直为增直到最后一个元素)，例如下题中的start_index控制回溯方向，每次回溯做出选择后持续向后一个元素做选择。

 class Solution:def subsetXORSum(self, nums: List[int]) -> int:def trace_back(item, start_index):if start_index == len(nums):ans.append(item)returntrace_back(item^nums[start_index], start_index + 1)trace_back(item, start_index + 1)ans = []trace_back(0, 0)print(ans)return sum(ans)

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:ans = []tem = []def trace_back(cur, n, k):if n - cur + 1 < k:returnif k == 0:ls = copy.deepcopy(tem)ans.append(ls)return tem.append(cur)trace_back(cur+1, n, k-1)tem.pop()trace_back(cur+1, n, k)trace_back(1, n, k)return ans

解存在问题
只收集一个结果或者判断是否存在问题，则收集bool结果
例如：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
如果 word 存在于网格中，返回 true ；否则，返回 false

 def exist(self, board: List[List[str]], word: str) -> bool:visited = {}rows = len(board)colums = len(board[0])n = len(word)def find_word(row, colum, k):if board[row][colum] != word[k]:return Falseif k == n - 1:return Trueresult = Falsevisited[(row, colum)] = Truefor (r, c) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:if 0 <= row + r < rows and 0 <= colum + c < colums:if not visited.get((row + r, colum + c), False):这里只要判断存在一个解立马退出后序遍历，返回结果,只需要判断是否存在解if find_word(row + r, colum + c, k + 1):result = Truebreakvisited[(row, colum)] = Falsereturn resultfor i in range(rows):for j in range(colums):if find_word(i, j, 0):return Truereturn False

所以解决回溯问题的算法步骤分为如下：

1. 找到求解结束条件
2. 判断选择方法，是否是可重复选择
3. 找到起始求解值