概念
类似穷举的方法，不断搜索可能解的路径，当发现不满足的条件时，就回溯返回，返回后再继续尝试别的路径。
(如下图示, 为了找到迷宫的出口，不断尝试不同的路径，当发现路径不通时，回溯到岔路口，并继续走其他路径)
基本思想
将上面的走迷宫进一步抽象，可以将这个问题转化成树结构，称之为解空间树。
解空间树和迷宫有如下对应关系：
根节点→初始状态
中间节点→分叉路口
不满足问题解的叶子节点→迷宫死路
满足问题解的叶子节点→迷宫出口
回溯法解题步骤
（1）针对所给问题，确定问题的解空间：
首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
（2）确定结点的扩展搜索规则
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数（在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程）避免无效搜索。
实现时的代码细节
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void backtrack(state s) {
if(s is end){ // 当前结点为可行解
sols.append(path); // 保存该解
}
else if(s has no ways){ // 当前结点为不可达叶子结点
return;
}
else{ // 当前结点为中间结点
for(i in possible ways){
next_s = do i in s; // 选择一条边
backtrack(next_s); // 在选择的边上往下走
s = redo i in s; // 回溯到父结点
}
}
}
|
例题
39. Combination Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
size = len(candidates)
if size == 0:
return []
# 剪枝的前提是数组元素排序
# 深度深的边不能比深度浅的边还小
# 要排序的理由：1、前面用过的数后面不能再用；2、下一层边上的数不能小于上一层边上的数。
candidates.sort()
# 在遍历的过程中记录路径，一般而言它是一个栈
path = []
res = []
# 注意要传入 size ，在 range 中， size 取不到
self.__dfs(candidates, 0, size, path, res, target)
return res
def __dfs(self, candidates, begin, size, path, res, target):
# 先写递归终止的情况
if target == 0:
# Python 中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
# 或者使用 path.copy()
res.append(path[:])
for index in range(begin, size):
residue = target - candidates[index]
// “剪枝”操作，不必递归到下一层，并且后面的分支也不必执行
if residue < 0:
break
path.append(candidates[index])
# 因为下一层不能比上一层还小，起始索引还从 index 开始
self.__dfs(candidates, index, size, path, res, residue)
path.pop()
#作者：liweiwei1419
#链接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
res = list()
def backtrack(index: int):
# 递归终止情况
if index == len(S) and len(res) >= 3:
return True
curr = 0
for i in range(index, len(S)):
# 两位以上的数字不能以0开头
if i > index and S[index] == "0":
break
# 截取字符串转化为数字
curr = curr * 10 + ord(S[i]) - ord("0")
# 如果截取的数字大于int的最大值，则终止截取
if curr > 2**31 - 1:
break
# 如果截取的数字大于res中前两个数字的和，说明这次截取的太大，直接终止，因为后面越截取越大
if len(res) > 2 and curr > res[-2] + res[-1]:
break
if len(res) <= 1 or curr == res[-2] + res[-1]:
res.append(curr)
if backtrack(i + 1):
return True
res.pop()
return False
backtrack(0)
return res
# https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/solution/javahui-su-suan-fa-tu-wen-xiang-jie-ji-b-vg5z/
|
java回溯算法图文详解，击败了100%的用户
回溯法是暴力解法的一个主要实现手段, 暴力解法可以通过多重循环实现,但是当n不定时,循环的层数也不固定,可能不能使用多重循环来暴力解,此时就只能使用回溯法.
参考资料
