05.回溯算法
# 00.回溯算法
- 回溯算法是一种通过
构建解的所有可能方案
并在必要时回退以寻找正确解
的算法 - 它通常用于
组合问题、排列问题、子集问题
和其他需要穷举所有可能解的情况 - 它通过
递归地尝试不同的选项
,并在当前路径不可能达到正确解时回退(撤销)操作
# 1、通用回溯
- 应用场景:组合、排列、子集等问题
- 普通的回溯算法通常会有一个显式的
for
循环,遍历每一个可能的选择(即选择列表
中的每一个元素) - 在遍历的过程中,算法会选择一个元素,进行递归调用,探索进一步的可能性,然后撤销选择,以便继续探索其他可能性
- 这里的核心在于“选择”步骤,通过循环实现对所有可能选择的逐一尝试
result = []
def _backtrace(选择列表, 路径):
if 满足结束条件:
result.append(路径)
return
for 选择 in 选择列表:
做选择
_backtrace(新的选择列表, 新的路径)
撤销选择
2
3
4
5
6
7
8
9
10
# 2、子集问题
- 场景:生成所有子集,不考虑顺序
result = []
def _backtrace(选择列表, start, 路径):
result.append(路径)
for i in range(start, len(选择列表)):
做选择
_backtrace(选择列表, i + 1, 新的路径)
撤销选择
2
3
4
5
6
7
8
# 3、全排列问题
- 场景:生成所有元素的排列组合,通常要求元素不能重复使用
result = []
def _backtrace(选择列表, 路径, used):
if 满足结束条件:
result.append(路径)
return
for i in range(len(选择列表)):
if used[i]:
continue
used[i] = True
做选择
_backtrace(选择列表, 新的路径, used)
撤销选择
used[i] = False
2
3
4
5
6
7
8
9
10
11
12
13
14
# 4、带剪枝回溯
- 场景:当问题可以提前判断某些路径不可能产生合法解时,可以在选择前进行“剪枝”操作,以减少计算量
result = []
def _backtrace(选择列表, 路径):
if 满足结束条件:
result.append(路径)
return
for 选择 in 选择列表:
if 剪枝条件:
continue
做选择
_backtrace(新的选择列表, 新的路径)
撤销选择
2
3
4
5
6
7
8
9
10
11
12
# 5、带状态恢复
- 场景:某些问题在回溯时需要恢复全局状态,以确保回溯后的状态与之前一致
result = []
def _backtrace(选择列表, 路径, 状态):
if 满足结束条件:
result.append(路径)
return
for 选择 in 选择列表:
if 剪枝条件:
continue
做选择并更新状态
_backtrace(选择列表, 新的路径, 更新后的状态)
恢复状态并撤销选择
2
3
4
5
6
7
8
9
10
11
12
# 01.子集类问题
- 特点:需要找出给定集合的所有子集,或在一定条件下生成符合条件的子集
# 0、子集问题
- 场景:生成所有子集,不考虑顺序
result = []
def _backtrace(选择列表, start, 路径):
result.append(路径)
for i in range(start, len(选择列表)):
做选择
_backtrace(选择列表, i + 1, 新的路径)
撤销选择
2
3
4
5
6
7
8
# 1、子集
给你一个整数数组
nums
,数组中的元素互不相同 返回该数组所有可能的子集解集不能包含重复的子集,你可以按 任意顺序 返回解集
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
输入:nums = [0]
输出:[[],[0]]
2
3
4
5
# 2、所有情况
当递归函数
backtrack
执行完毕时,会回到它被调用的位置,继续执行该位置之后的语句在
for
循环中,控制流回到backtrack(i + 1, path)
语句之后,即path.pop()
处path.pop()
执行完后,控制流继续for
循环如果
i
已经是最后一个元素,循环结束,函数返回到上一层
- 推演
# 1) 初始调用:
backtrack(0, []) 进入 for 循环,i 为 0,path 变为 [1]
递归调用 backtrack(1, [1])
# 2) 递归层级 1:
backtrack(1, [1]) 进入 for 循环,i 为 1,path 变为 [1, 2]
递归调用 backtrack(2, [1, 2])
# 3) 递归层级 2:
backtrack(2, [1, 2]) 进入 for 循环,i 为 2,path 变为 [1, 2, 3]
递归调用 backtrack(3, [1, 2, 3])
因为 start = 3,不满足 i < len(nums),因此直接返回
# 4) 回溯到递归层级 2:
从 backtrack(3, [1, 2, 3]) 返回,执行 path.pop(),path 变回 [1, 2]
返回后,控制流回到 for 循环中的下一行,即 backtrack(2, [1, 2]) 中的 for i in range(start, len(nums))
由于 i = 2,已经是循环的最后一次,所以退出 for 循环,函数返回到上一层
# 5)回溯到递归层级 1:
从 backtrack(2, [1, 2]) 返回,执行 path.pop(),path 变回 [1]
控制流回到 for i in range(start, len(nums)) 中,继续循环,此时 i = 2,继续执行 path.append(nums[i]),path 变为 [1, 3]
# 6)再次进入递归层级 2:
递归调用 backtrack(3, [1, 3])
因为 start = 3,直接返回,执行 path.pop(),path 变回 [1]
# 7)继续回溯:
从 backtrack(3, [1, 3]) 返回,i = 2 是 for 循环中的最后一项,循环结束,函数返回到 backtrack(1, [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
# 3、python
- 每次进入
backtrack
函数时,都会将当前的子集path
加入到结果result
中 - 使用
for
循环从start
开始遍历nums
,依次尝试将每个元素加入到当前子集中 - 对于每个元素,先加入
path
,然后递归调用backtrack
以生成包括当前元素的子集 - 递归完成后,使用
path.pop()
进行回溯,移除当前元素,继续生成不包括当前元素的子集
class Solution:
def subsets(self, nums):
res = []
def dfs(start, path):
res.append(path[:]) # 每次进入函数时,都将当前路径(子集)添加到结果集中
for i in range(start, len(nums)): # 从start开始遍历,尝试构建不同的子集
path.append(nums[i]) # 将当前元素加入到路径(子集)中
dfs(i + 1, path) # 递归调用dfs,继续构建包含当前元素的子集
path.pop() # 回溯:移除当前元素,尝试构建不包含当前元素的子集
dfs(0, []) # 初始调用时,路径为空,开始索引为0
return res
print(Solution().subsets([1, 2, 3])) # 输出:[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
2
3
4
5
6
7
8
9
10
11
12
13
时间复杂度:
O(n \* 2^n)
生成所有子集的复杂度
: 每个元素可以选择在或不在某个子集中,因此有2^n
个子集。
构建每个子集的复杂度
: 每次生成一个子集时,算法最多需要遍历n
个元素。空间复杂度:
O(n * 2^n)
- 最终结果
res
中包含2^n
个子集,每个子集的最大长度为n
- 所以存储这些子集的空间复杂度为
O(n * 2^n)
# 02. 生成结构类问题
- 特点:生成符合特定规则的结构或模式
# 0、通用回溯
- 应用场景:组合、排列、子集等问题
- 普通的回溯算法通常会有一个显式的
for
循环,遍历每一个可能的选择(即选择列表
中的每一个元素) - 在遍历的过程中,算法会选择一个元素,进行递归调用,探索进一步的可能性,然后撤销选择,以便继续探索其他可能性
- 这里的核心在于“选择”步骤,通过循环实现对所有可能选择的逐一尝试
result = []
def _backtrace(选择列表, 路径):
if 满足结束条件:
result.append(路径)
return
for 选择 in 选择列表:
做选择
_backtrace(新的选择列表, 新的路径)
撤销选择
2
3
4
5
6
7
8
9
10
# 1、生成括号
- 特点:生成符合特定规则的结构或模式
- 22.括号生成 (opens new window)
- 数字
n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合 1 <= n <= 8
# 输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
# 输入:n = 1
输出:["()"]
2
3
4
# 2、所有情况
- 首先考虑生成所有的情况,每一层都在上一层的基础上加上一个左括号或者右括号,直到达到2n的长度为止
class Solution:
def generateParenthesis(self, n):
res = []
def dfs(s):
if len(s) == n * 2:
res.append(s)
return # 到达终止条件 记得return
dfs(s + '(',)
dfs(s + ')')
dfs('')
return res
print( Solution().generateParenthesis(2) )
"""
[
'((((', '((()', '(()(', '(())',
'()((', '()()', '())(', '()))',
')(((', ')(()', ')()(', ')())',
'))((', '))()', ')))(', '))))'
]
"""
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 3、python
- 虽然
generate
函数没有显式的for
循环,但是它通过两个条件判断递归地做出了两种选择,相当于隐式地进行了选择的遍历
- 因此,递归的每一层都相当于一个
for
循环在遍历这两种可能性
class Solution:
def generateParenthesis(self, n):
res = [] # 存储所有有效的括号组合
def dfs(s, l, r):
if len(s) == n * 2: # 长度达到 2n 时加入结果列表
res.append(s)
return
if l < n: # 如果左括号数量小于 n
dfs(s + '(', l + 1, r)
# 如果右括号数量大于左括号数量肯定不符合,不进入循环即可
if r < l:
dfs(s + ')', l, r + 1)
dfs('', 0, 0)
return res
2
3
4
5
6
7
8
9
10
11
12
13
14
15
时间复杂度:
O(4^n / sqrt(n))
- 每次递归调用可能会生成两个新的递归分支,因此在最坏情况下会有
2^n
个递归调用- 但由于有效组合的数量受到卡塔兰数的限制,实际生成的组合数远少于
2^n
空间复杂度:
O(C(n) * n)
其中 C(n) 是 Catalan(卡塔兰数)
- 结果列表
res
存储C_n
个有效的括号组合,每个组合的长度为2n
,因此存储结果的空间复杂度为O(n * C_n)
# 03.组合类问题
- 特点:需要从给定的元素集合中挑选出满足特定条件的组合,重点在于选或不选某个元素
# 0、通用回溯
result = []
def _backtrace(选择列表, 路径):
if 满足结束条件:
result.append(路径)
return
for 选择 in 选择列表:
做选择
_backtrace(新的选择列表, 新的路径)
撤销选择
2
3
4
5
6
7
8
9
10
# 1、组合总和
给你一个 无重复元素 的整数数组
candidates
和一个目标整数target
找出
candidates
中可以使数字和为目标数target
的 所有 不同组合 ,并以列表形式返回你可以按 任意顺序 返回这些组合
candidates
中的 同一个 数字可以 无限制重复被选取如果至少一个数字的被选数量不同,则两种组合是不同的
对于给定的输入,保证和为
target
的不同组合数少于150
个
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
输入: candidates = [2], target = 1
输出: []
2
3
4
5
6
7
8
# 2、所有情况
class Solution:
def combinationSum(self, candidates, target):
nums = candidates
def dfs(start, path, k):
res.append(list(path))
if k < 0: # 减去后剩余部分小于0,证明不存在
return
for i in range(start, len(nums)):
path.append(nums[i]) # 选择当前数字
dfs(i, path, k - nums[i]) # 因为数字可以重复使用,所以下一层递归仍从当前索引开始
path.pop()
nums.sort()
res = []
dfs(0, [], target)
return res
print(Solution().combinationSum([2, 3], 4))
# [[], [2], [2, 2], [2, 2, 2], [2, 2, 3], [2, 3], [3], [3, 3]]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 3、python
排序候选数组:虽然排序不是必须的,但排序有助于提前终止搜索,从而优化性能
回溯函数:定义一个回溯函数
backtrack
,该函数接收当前组合、剩余目标值和当前处理的候选数组起始索引递归探索:
- 对于每个候选数字,首先检查是否可以继续加入当前组合(即剩余目标值减去当前数字不小于0)
- 然后递归调用回溯函数以探索进一步的组合
剪枝:
- 如果当前剩余的目标值为0,表示找到一个有效组合,将其加入结果集中
- 否则,如果目标值小于0,则终止当前路径的探索
class Solution:
def combinationSum(self, candidates, target):
nums = candidates
def dfs(start, path, k):
if k == 0:
res.append(list(path))
return
elif k < 0: # 如果目标值小于0,终止搜索
return
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i, path, k - nums[i]) # 因为数字可以重复使用,所以下一层递归仍从当前索引开始
path.pop()
nums.sort()
res = []
dfs(0, [], target)
return res
print(Solution().combinationSum([2, 3, 5], 8)) # 输出 [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
时间复杂度可以达到
O(target^m)
,其中m
是递归树的深度
- 在每一层递归中,算法会尝试从
start
到len(nums)
的所有可能选择,因此每一层的分支数量取决于当前的选择数- 最坏情况下,递归树的每一层都有
len(nums)
个分支- 最深的递归深度是
target // min(nums)
,因为最坏情况下每次只减去最小的候选值min(nums)
空间复杂度
- 结果列表
res
存储了所有可能的组合,每个组合的元素数量和组合数目都可能非常大- 因此存储结果的空间复杂度也是
O(组合数量 \* 组合大小)
,但这具体依赖于输入数据
# 04.排列类问题
- 特点:涉及元素的顺序安排,通常需要生成所有可能的排列
# 0、全排列问题
- 场景:生成所有元素的排列组合,通常要求元素不能重复使用
result = []
def _backtrace(选择列表, 路径, used):
if 满足结束条件:
result.append(路径)
return
for i in range(len(选择列表)):
if used[i]:
continue
used[i] = True
做选择
_backtrace(选择列表, 新的路径, used)
撤销选择
used[i] = False
2
3
4
5
6
7
8
9
10
11
12
13
14
# 1、全排列
给定一个不含重复数字的数组
nums
,返回其 所有可能的全排列 你可以 按任意顺序 返回答案
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
2
3
4
5
6
7
8
# 2、所有情况
- 时间复杂度为
O(n * n!)
- 生成一个排列需要遍历列表中的每个元素,并且有
n!(1*2*3*n!)
种不同的排列 - 对于每一个排列,生成的过程涉及递归深度为
n
,并且每层递归都需要遍历所有n
个元素
- 生成一个排列需要遍历列表中的每个元素,并且有
- 空间复杂度为
O(n)
加上结果存储的空间O(n * n!)
- 递归栈空间: 由于递归调用的深度为
n
,因此递归栈空间的复杂度为O(n)
- 附加存储空间: 需要一个数组来跟踪哪些元素已经被使用 (
used
数组),以及保存当前排列 (path
数组),这些也都是O(n)
的空间 - 结果存储空间: 生成的所有排列需要存储,占用
O(n * n!)
的空间
- 递归栈空间: 由于递归调用的深度为
对于一个给定的数组,DFS会从头到尾依次选择一个元素作为排列的一部分
然后对剩余元素继续递归,直到生成一个完整的排列当所有排列都生成后,递归结束
# 3、python
- 递归函数
dfs
:path
保存当前排列路径,used
是一个布尔数组,标记哪些元素已经被使用过,res
是存放所有排列结果的列表 - 在递归函数中,我们遍历
nums
的每一个元素,通过检查used[i]
是否为False
,判断该元素是否已经被使用过 - 如果未被使用,则将其加入
path
并标记为已使用,继续递归处理剩下的元素 - 在递归返回后,通过
pop()
和used[i] = False
撤销选择,进行回溯 - 为什么全排列不需要传入start
- 在子集问题中,
start
参数的作用是避免重复选择已经考虑过的元素,从而防止生成重复的子集 - 在排列问题中,每一个排列都是有序的,每个位置都需要尝试放入所有可能的元素
- 在子集问题中,
class Solution:
# path(排列路径)user(哪些使用过) res(排列结果列表)
def permute(self, nums):
def dfs(path, used):
if len(path) == len(nums): # 找到一个完整的排列
res.append(path[:]) # path[:] 创建了一个浅拷贝
return
# 遍历每个数字,尝试将其加入当前排列路径中
for i in range(len(nums)):
if used[i]: # 如果当前数字被使用过 跳过
continue
path.append(nums[i]) # 选择当前数字
used[i] = True
dfs(path, used) # 递归处理剩余的数字
path.pop() # 回溯:撤销选择
used[i] = False
res = []
used = [False] * len(nums)
dfs([], used)
return res
nums = [1, 2, 3]
print(Solution().permute(nums))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
""" # 如果没有used 判断结果会打印如下
[
[1, 1, 1], [1, 1, 2], [1, 1, 3],
[1, 2, 1], [1, 2, 2], [1, 2, 3],
[1, 3, 1], [1, 3, 2], [1, 3, 3],
[2, 1, 1], [2, 1, 2], [2, 1, 3],
[2, 2, 1], [2, 2, 2], [2, 2, 3],
[2, 3, 1], [2, 3, 2], [2, 3, 3],
[3, 1, 1], [3, 1, 2], [3, 1, 3],
[3, 2, 1], [3, 2, 2], [3, 2, 3],
[3, 3, 1], [3, 3, 2], [3, 3, 3]
]
"""
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
38
39
40
41
42
43
时间复杂度:
O(n * n!)
- 对于一个长度为
n
的数组nums
,其所有排列的数量是n!
(n
的阶乘)- 生成每个排列需要进行
n
层递归,每层递归要遍历n
个元素,因此总体时间复杂度为O(n * n!)
空间复杂度:
O(n * n!)
- 结果列表
res
中存储了n!
个排列,每个排列的长度为n
,因此存储结果的空间复杂度为O(n * n!)
# 05.分割类问题
- 特点:将输入(如字符串或数组)分割成若干符合条件的部分
# 0、带状态恢复
- 场景:某些问题在回溯时需要恢复全局状态,以确保回溯后的状态与之前一致
- 回溯:核心逻辑是使用递归函数
dfs(i)
来遍历所有可能的回文分割路径,并在找到有效分割时将其存储到结果列表中 - 带状态恢复的回溯:主要用于记录当前的选择路径,并在递归返回时恢复到之前的状态
result = []
def _backtrace(选择列表, 路径, 状态):
if 满足结束条件:
result.append(路径)
return
for 选择 in 选择列表:
if 剪枝条件:
continue
做选择并更新状态
_backtrace(选择列表, 新的路径, 更新后的状态)
恢复状态并撤销选择
2
3
4
5
6
7
8
9
10
11
12
# 1、分割回文串
- 131.分割回文串 (opens new window)
- 给你一个字符串
s
,请你将s
分割成一些子串,使每个子串都是回文串,返回s
所有可能的分割方案
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
2
# 2、所有情况
- 将字符串切分结果展开成一棵树以后,可以发现结果集就是对这棵树进行dfs深度优先搜索的遍历结果
class Solution:
def partition(self, s):
def dfs(start, path):
if start == len(s):
ret.append(path[:]) # 如果到达字符串末尾,说明找到一个有效分割方案,存储下来
return
for i in range(start, len(s)):
path.append(s[start: i + 1])
dfs(i + 1, path)
path.pop() # 回溯,撤销选择
ret = []
dfs(0, []) # 从第 0 个位置开始进行回溯
return ret
print(Solution().partition("aab"))
"""
[
['a', 'a', 'b'],
['a', 'ab'],
['aa', 'b'],
['aab']
]
"""
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
# 3、python
- 将字符串切分结果展开成一棵树以后,可以发现结果集就是对这棵树进行dfs深度优先搜索的遍历结果
- 对所有分割方案挨个进行回文判断,最后找到所有可能性
class Solution:
def partition(self, s):
ret = [] # ret 用于存储所有的分割方案
def dfs(start, path):
if start == len(s):
ret.append(path[:]) # 如果到达字符串末尾,说明找到一个有效分割方案,存储下来
return
for i in range(start, len(s)):
if is_palindrome(s, start, i): # 检查子串 s[i:j+1] 是否为回文
path.append(s[start: i + 1])
dfs(i + 1, path)
path.pop() # 回溯,撤销选择
def is_palindrome(s, left, right): # 检查子串 s[left:right+1] 是否为回文
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
dfs(0, []) # 从第 0 个位置开始进行回溯
return ret
print(Solution().partition("aab")) # 输出 [['a', 'a', 'b'], ['aa', 'b']]
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
时间复杂度:近于
O(n * 2^n)
, 其中n
是字符串的长度
- 每个字符都有可能成为一个单独的回文子串,或者是多个字符组合成的回文子串
- 因此,可能的划分方式数量非常多,接近于划分问题的
2^n
次方复杂度- 判断回文的次数 时间复杂度是
O(n)
空间复杂度:
O(n * 2^n)
- 结果列表
ret
中存储了所有的有效分割方案- 如果所有字符都是回文子串,那么每个字符都可以形成一个单独的子串,这样的分割方案的数量为
2^(n-1)