回溯算法
原文链接:note.noxussj.top/?sou...
介绍
回溯算法是算法设计中的一种方法。回溯算法是一种渐进式寻找并构建问题解决方式的策略。回溯算法会先从一个可能的动作开始解决问题,如果不行,就回溯并选择另一个动作,直到将问题解决。
就像你在一个迷宫里面遇到了当前有三条岔路,你选择了第一条后发现此路不通,那你是不是要回到原点,进行选择第二条道路,以此类推,最后选择一条正确的道路。
什么问题适合用回溯算法解决?
- 有很多分岔路
- 这些路里面有死路,也有出路
- 通常需要用递归来模拟所有的路
基础案例
场景一
全排列
// 输入
const input = [1, 2, 3]
// 输出
const output = [
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]
]
步骤:
- 用递归模拟所有出路的情况
- 遇到包含重复元素的情况,就回溯
- 收集所有到达递归终点的情况并返回
原文链接:note.noxussj.top/?sou...
本网站是一个以CSS、JavaScript、Vue、HTML为核心的前端开发技术网站。我们致力于为广大前端开发者提供专业、全面、实用的前端开发知识和技术支持。 在本网站中,您可以学习到最新的前端开发技术,了解前端开发的最新趋势和最佳实践。我们提供丰富的教程和案例,让您可以快速掌握前端开发的核心技术和流程。 本网站还提供一系列实用的工具和插件,帮助您更加高效地进行前端开发工作。我们提供的工具和插件都经过精心设计和优化,可以帮助您节省时间和精力,提升开发效率。 除此之外,本网站还拥有一个活跃的社区,您可以在社区中与其他前端开发者交流技术、分享经验、解决问题。我们相信,社区的力量可以帮助您更好地成长和进步。 在本网站中,您可以找到您需要的一切前端开发资源,让您成为一名更加优秀的前端开发者。欢迎您加入我们的大家庭,一起探索前端开发的无限可能!