前端之算法（九）回溯算法

大家好，今天我们要聊的是回溯算法这种方法，它和贪心算法、分而治之、动态规划一样，也是算法设计中的一种方法，你同样可以把它当作解决问题的一种思路。接下来让我来看看回溯算法是什么？

回溯算法

• 回溯算法是算法设计中的一种能方法。

• 回溯算法是一种渐进式寻找并构建问题解决方式的策略。

• 回溯算法会先从一个可能的动作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决。

可能说起来有点抽象，举个栗子。</br></br>《鬼吹灯之寻龙诀》相信大家都看过，众所都周知这是一部探险和盗墓题材的影视作品，里面有很多山洞，陵墓等的探险情节，在探险的过程中，往往会遇到很多岔路。如果你是摸金校尉的话，你会怎么办？是不是先选择一条岔路，如果走不通。我们就回溯到原点，再继续下一条路，继续尝试，直到找到出口。这个逻辑就是回溯算法。回溯就是指一套路没走通，再拐回来，这个拐回来就是回溯。

那什么问题适合用回溯算法解决呢？

• 有很多路。这个路可以是矩阵，树的某个路径，也可以是某种组合。

• 这些路里，有死路，也有出路。死路就是指符合要求的答案，出路就是指符合要求的答案。

• 通常需要递归来模拟所有的路。

全排列

说了那么多理论，我们来一个实际的例子吧！

什么是全排列呢？

• 就是你输入一组数，他输出这组数所有不重复的排序组合。

步骤

• 用递归模拟出所有情况。

• 遇到包含重复元素的情况，就回溯。

• 收集所有达到递归终点的情况，并返回。

• 代码如下：

function permute(nums: number[]): number[][] {    const res:number[][] = []    const backtrack = (path: number[]) => {        if(path.length === nums.length) {            res.push(path)            return        }        nums.forEach(n => {            if(path.includes(n)) return            backtrack(path.concat(n))        })    }    backtrack([])    return res;};

End~~