定义
回溯算法实际上**基于DFS(深度优先搜索)**的一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回到上一个状态，尝试其他的路径，这种走不通就退回再走的技术为回溯法；满足回溯条件的某个状态的点称为“回溯点”。
回溯相关问题
- DFS 和回溯算法区别
DFS 是一个劲的往某一个方向搜索,直到到达最底层，而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置。
- 何时使用回溯算法
当问题碰到走不通的路径，需要"回头"，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止。
- 回溯算法的基本步骤
- 找到状态变量(回溯函数的参数)
- 依据题意定义递归结束条件
- 找准选择列表(与函数参数相关),与第一步紧密关联
- 判断是否需要剪枝，即提前将不符合条件的路径排除掉
- 作出选择，递归调用，进入下一层
- 撤销选择
- 回溯算法类的题型有哪些
- 子集、组合类问题
- 排列类问题
- 搜索、N皇后类问题、
注意:子集、组合是无关顺序的，而排列是和元素顺序有关的，如 [1，2] 和 [2，1] 是同一个组合(子集)，但 [1,2] 和 [2,1] 是两种不一样的排列！！！！
回溯算法的通用模板
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择
题目举例
Leetcode78.子集
问题描述
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
**说明：**解集不能包含重复的子集。
示例
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
python代码题解
套用上述回溯算法的模板，path表示已选择的路径，for i in range(start, len(nums))表示当前能够选择的列表元素，注意对于组合类问题不能够选择前面已经选择过的元素，因为会存在重复结果，因此必须有一个start参数来控制每一轮能够选择的元素[start, len(nums)]。
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: def backtrack(nums, path, start): # 将path添加到res结果中 res.append(path.copy()) # 当前能够选择的参数列表 for i in range(start, len(nums)): # 做选择 path.append(nums[i]) backtrack(nums, path, i+1) # 撤销选择 path.pop() res = [] backtrack(nums, [], 0) return res
Leetcode77.组合
问题描述
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
python代码题解
本题与上一题基本相同，都是属于组合类问题，只是递归的终止条件不同，本题的终止条件是当路径长度为k时len(track) == k，将结果添加到res中。
套用上述回溯算法的模板，track表示已选择的路径，for i in range(start, n+1)表示当前能够选择的列表元素，注意start是从1开始的，应为题目中指明能够选择的数为1...n。
class Solution: def combine(self, n: int, k: int) -> List[List[int]]: # 数的选择范围在1-n def backtrack(n,k,start,track): if len(track) == k: res.append(track.copy()) return # 注意i从start开始递增 for i in range(start, n+1): # 做选择 track.append(i) backtrack(n,k,i+1,track) # 撤销选择 track.pop() res = [] track = [] backtrack(n,k,1,track) return res
通过上述讲解，读者应该对回溯算法的概念以及模板套路有一个基本的认识，回溯的关键在于选择与撤销选择的过程，读者可以仔细体会一下 ，相信一定会有所收获。后续会继续更新关于回溯算法的相关题解，欢迎持续关注！
