题目形式很简单 就是输出一个数组的全排列 这个题在前端面试中提问频率很高 因为要解决这个问题需要用到一个算法中很重要的思想

回溯

关于回溯我们有三个步骤 不可或缺

1.递归函数参数

2.单层搜索逻辑

3.递归终止条件

把这三个步骤搞清楚了 回溯算法也就几乎完成了

思路分析(以数组[1, 2, 3]为例)

1.每一位都有三种选择

2.每一次都做选择 展开出一颗空间树 如下图

3.利用约束条件(不能重复选) 做剪枝 减去不会产生正确解的选项分支 利用hashMap即可

为什么要回溯?

我们不是找到一个排列就结束了 要找出所有满足条件的排列

当一个递归调用结束 结束的是当前的递归分支 还要去别的分支继续搜索

所以 要撤销当前的选择 回到选择前的状态 再选择下一个选项 (进入下一个分支)

往map存入的当前选择也要撤销 表示撤销这个选择

退回来 把路走全 才能再一棵树空间中 回溯出所有的解

递归函数实现

1.递归入口: 传入空数组path 什么都没选

2.单层循环规则: 循环枚举所有选项 判断是否跳过某个分支 每一轮迭代做出一个选择(基于它 继续选)

3.递归出口: 当构建的path数组长度等于nums数组长度就够了 加入res数组

源代码贴在下面

为什么加入解集时，要将数组内容拷贝到一个新的数组里，再加入解集？

因为该 path 变量存的是地址引用，结束当前递归时，将它加入 res 后，该算法还要进入别的递归分支继续搜索，还要继续将这个 path 传给别的递归调用，它所指向的内存空间还要继续被操作，所以 res 中的 path 的内容会被改变，这就不对
所以要弄一份当前的拷贝，放入 res，这样后续对 path 的操作，就不会影响已经放入 res 的内容

我根据回溯算法详细画出了函数的运行顺序以及hashMap和path数组的变化 帮助理解回溯的运行顺序