课程名称：JavaScript版数据结构与算法
课程章节：第15章 算法设计思想之“回溯算法”
主讲老师：lewis
课程内容：
今天学习的内容包括：
15-1 回溯算法简介——回溯算法是一中渐进式寻找并构建问题解决方式的策略。
15-2 LeetCode：46. 全排列——通过回溯算法和递归实现全排列。
课程收获：
回溯算法简介
回溯算法是什么？
- 回溯算法是算法设计中的一种方法。
- 回溯算法是一种渐进式寻找并构建问题解决方式的策略。
- 回溯算法会先从一个可能的动作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决。
什么问题适合用回溯算法解决？
- 有很多路。
- 有些路里，有死路，也有出路。
- 通常需要递归来模拟所有的路。
全排列
- 用递归模拟出所有情况。
- 遇到包含重复元素的情况，就回溯。
- 收集所有到达递归终点的情况，并返回。
46. 全排列
解题思路
- 要求：1、所有排列情况；2、没有重复元素。
- 有出路、有思路。
- 考虑使用回溯算法。
解题步骤
- 用递归模拟出所有的情况。
- 遇到包含重复元素的情况，就回溯。
- 收集所有到达递归终点的情况，并返回。
性能分析
- 时间复杂度：O(n!)，n!=1 * 2 * 3 * … * (n-1) * n。
- 空间复杂度：O(n)。
今天 通过 回溯算法 学习了 全排列，回溯算法一种渐进式寻找并构建问题解决方式的策略，遇到重复的数值就回溯。对自己说一句，加油😀~
坚持打卡，坚持学习！明天见💪~