当前位置：首页 > article >正文

回溯算法学习记录及习题集合

article 2025/3/4 0:50:14

一、引言

在算法领域，回溯算法是一种非常经典的算法思想。它主要用于解决组合问题、排列问题、切割问题等。回溯算法的核心是递归和试探，通过不断尝试找到问题的解。本文将带您深入了解回溯算法的原理及应用。

自学用来记录回溯算法的，大佬略过。
学习的去看网上资料 labuladong算法笔记或卡尔的代码随想录。

二、什么是回溯算法

回溯算法是一种试探性的算法，它从一个可能的动作开始，尝试搜索所有可能的动作，直到找到解决方案。如果当前路径无法找到解决方案，它会返回上一步，尝试其他路径。这个过程称为“回溯”。

三、回溯法的效率

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。
如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
一些问题能暴力搜出来就不错了，再剪枝一下，还没有更高效的解法。

四、回溯法解决的问题

上题目，如何理解回溯算法？做，做，做。
这里挑了代码随想录里的习题+leetcode热题100中的回溯题。

leetcode热题100

46 全排列
78 子集
17 电话号码的组合
39. 组合总和
79. 单词搜索
22. 括号生成
131. 分割回文串
51. N 皇后

代码随想录(去掉上面重复的)

77 组合
216.组合总和III
40.组合总和II
131.分割回文串
93.复原IP地址
78.子集
90.子集II
491.递增子序列
47.全排列 II
332.重新安排行程
37. 解数独

回溯法，一般可以解决如下几种问题：
组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

五、回溯算法的基本步骤

您提供的代码模板已经很清晰地描述了回溯算法的核心步骤。以下是对应的文字解释：

def backtracking(参数) {
    // 参数通常包括当前路径、选择列表等

    if (终止条件) {
        // 如果当前路径满足问题的解的条件，则将解存放起来
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        // 遍历所有可能的选择

        处理节点;
        // 这通常意味着将当前选择添加到路径中

        backtracking(路径，选择列表); // 递归
        // 递归调用以继续探索基于当前选择的路径

        回溯，撤销处理结果
        // 这通常意味着从路径中移除最后添加的选择，以便尝试其他选择
    }
}