2022年 12月 19日

算法之【回溯算法】详解(python)

回溯算法

定义

回溯算法实际上**基于DFS(深度优先搜索)**的一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回到上一个状态,尝试其他的路径,这种走不通就退回再走的技术为回溯法;满足回溯条件的某个状态的点称为“回溯点”。

回溯相关问题

  1. DFS 和回溯算法区别

DFS 是一个劲的往某一个方向搜索,直到到达最底层,而回溯算法建立在 DFS 基础之上的,但不同的是在搜索过程中,达到结束条件后,恢复状态,回溯上一层,再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置

  1. 何时使用回溯算法

当问题碰到走不通的路径,需要”回头”,以此来查找出所有的解的时候,使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通),要撤销选择,回退到上一个状态,继续尝试,直到找出所有解为止。

  1. 回溯算法的基本步骤
  • 找到状态变量(回溯函数的参数)
  • 依据题意定义递归结束条件
  • 找准选择列表(与函数参数相关),与第一步紧密关联
  • 判断是否需要剪枝,即提前将不符合条件的路径排除掉
  • 作出选择,递归调用,进入下一层
  • 撤销选择
  1. 回溯算法类的题型有哪些
  • 子集、组合类问题
  • 排列类问题
  • 搜索、N皇后类问题、

注意:子集、组合是无关顺序的,而排列是和元素顺序有关的,如 [1,2] 和 [2,1] 是同一个组合(子集),但 [1,2] 和 [2,1] 是两种不一样的排列!!!!

回溯算法的通用模板

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

题目举例

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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

Leetcode77.组合

问题描述

给定两个整数 nk,返回 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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

通过上述讲解,读者应该对回溯算法的概念以及模板套路有一个基本的认识,回溯的关键在于选择与撤销选择的过程,读者可以仔细体会一下 ,相信一定会有所收获。后续会继续更新关于回溯算法的相关题解,欢迎持续关注!

如果喜欢作者,欢迎点赞、收藏及关注,谢谢!

欢迎扫描下面二维码关注公众号:阿旭算法与机器学习, 和作者共同学习交流。
在这里插入图片描述