不做大哥好多年
xiaonaiqiang
2024-08-26
目录

05.回溯算法

回溯算法是一种通过构建解的所有可能方案并在必要时回退以寻找正确解的算法

它通常用于组合问题、排列问题、子集问题和其他需要穷举所有可能解的情况

它通过递归地尝试不同的选项，并在当前路径不可能达到正确解时回退（撤销）操作

# 00.回溯算法

# 1、通用回溯

  • 应用场景：组合、排列、子集等问题
  • 普通的回溯算法通常会有一个显式的 for 循环，遍历每一个可能的选择（即选择列表中的每一个元素）
  • 在遍历的过程中，算法会选择一个元素，进行递归调用，探索进一步的可能性，然后撤销选择，以便继续探索其他可能性
  • 这里的核心在于“选择”步骤，通过循环实现对所有可能选择的逐一尝试
result = []
def _backtrace(选择列表, 路径):
    if 满足结束条件:
        result.append(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        _backtrace(新的选择列表, 新的路径)
        撤销选择
1
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, 新的路径)
        撤销选择
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
1
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(新的选择列表, 新的路径)
        撤销选择
1
2
3
4
5
6
7
8
9
10
11
12

# 5、带状态恢复

  • 场景：某些问题在回溯时需要恢复全局状态，以确保回溯后的状态与之前一致
result = []
def _backtrace(选择列表, 路径, 状态):
    if 满足结束条件:
        result.append(路径)
        return
    
    for 选择 in 选择列表:
        if 剪枝条件:
            continue
        做选择并更新状态
        _backtrace(选择列表, 新的路径, 更新后的状态)
        恢复状态并撤销选择
1
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, 新的路径)
        撤销选择
1
2
3
4
5
6
7
8

# 1、子集

  • 78.子集 (opens new window)

  • 给你一个整数数组 nums ，数组中的元素互不相同 返回该数组所有可能的子集

  • 解集不能包含重复的子集，你可以按 任意顺序 返回解集

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

输入：nums = [0]
输出：[[],[0]]
1
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]) 的调用位置
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]]
1
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(新的选择列表, 新的路径)
        撤销选择
1
2
3
4
5
6
7
8
9
10

# 1、生成括号

  • 特点：生成符合特定规则的结构或模式
  • 22.括号生成 (opens new window)
  • 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合
  • 1 <= n <= 8
# 输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
# 输入：n = 1
输出：["()"]
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) )
"""
[
    '((((', '((()', '(()(', '(())', 
    '()((', '()()', '())(', '()))', 
    ')(((', ')(()', ')()(', ')())', 
    '))((', '))()', ')))(', '))))'
]
"""
1
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
1
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(新的选择列表, 新的路径)
        撤销选择
1
2
3
4
5
6
7
8
9
10

# 1、组合总和

  • 39.组合总和 (opens new window)

  • 给你一个 无重复元素 的整数数组 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
输出: []
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]]
1
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]]
1
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 1、全排列

输入：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]
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]
]
"""
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
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(选择列表, 新的路径, 更新后的状态)
        恢复状态并撤销选择
1
2
3
4
5
6
7
8
9
10
11
12

# 1、分割回文串

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
1
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']
]
"""
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

# 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']]
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

时间复杂度：近于 O(n * 2^n)， 其中 n 是字符串的长度

  • 每个字符都有可能成为一个单独的回文子串，或者是多个字符组合成的回文子串
  • 因此，可能的划分方式数量非常多，接近于划分问题的 2^n 次方复杂度
  • 判断回文的次数 时间复杂度是 O(n)

空间复杂度：O(n * 2^n)

  • 结果列表 ret 中存储了所有的有效分割方案
  • 如果所有字符都是回文子串，那么每个字符都可以形成一个单独的子串，这样的分割方案的数量为 2^(n-1)
上次更新: 2024/10/15 16:27:13
04.算法模型
06.动态规划

← 06.动态规划→

最近更新
01
16.CAP
09-27
02
13.HTTP协议
09-25
03
12.TCP协议
09-25
更多文章>
Theme by Vdoing | Copyright © 2019-2024 逍遥子 技术博客 京ICP备2021005373号