关于leetcode:LeetCode-46-全排列算法

转自：https://leetcode-cn.com/probl…

思路
每一位都有 3 种抉择：1、2、3。

每一次都做抉择，开展出一棵空间树，如下图。

利用约束条件「不能反复选」，做剪枝，剪去不会产生正确解的选项（分支）。

利用 hashMap，记录选过的数，下次遇到雷同的数，跳过。
这样就不会进入「不会得出解的分支」，不做有效的搜寻。

怎么写递归函数
咱们要在这个蕴含解的空间树上，用 DFS 的形式搜寻出所有的解。

dfs 函数：基于以后的 path，持续选数，直到构建出非法的 path，退出解集。

递归的入口：dfs 执行传入空 path，什么都还没选。

函数体内，用 for loop 枚举出以后所有的选项，并用 if 语句跳过剪枝项。

每一轮迭代，作出一个抉择，基于它，持续选（递归调用）。
递归的进口：当构建的 path 数组长度等于 nums 长度，就选够了，退出解集。

为什么要回溯
咱们不是找到一个排列就完事，要找出所有满足条件的排列。

当一个递归调用完结，完结的是以后的递归分支，还要去别的分支持续搜。

所以，要撤销以后的抉择，回到抉择前的状态，再选下一个选项，即进入下一个分支。

留神，往 map 存入的以后抉择也要撤销，示意撤销这个抉择。

退回来，把路走全，能力在一棵空间树中，回溯出所有的解。

代码
jsgo

const permute = (nums) => {

const res = [];
const used = {};

function dfs(path) {if (path.length == nums.length) { // 个数选够了
        res.push(path.slice()); // 拷贝一份 path，退出解集 res
        return;                 // 完结以后递归分支
    }
    for (const num of nums) { // for 枚举出每个可选的选项
        // if (path.includes(num)) continue; // 别这么写！查找是 O(n)，减少工夫复杂度
        if (used[num]) continue; // 应用过的，跳过
        path.push(num);         // 抉择以后的数，退出 path
        used[num] = true;       // 记录一下 应用了
        dfs(path);              // 基于选了以后的数，递归
        path.pop();             // 上一句的递归完结，回溯，将最初选的数 pop 进去
        used[num] = false;      // 撤销这个记录
    }
}

dfs([]); // 递归的入口，空 path 传进去
return res;

};
解答评论区的困惑
为什么退出解集时，要将数组内容拷贝到一个新的数组里，再退出解集？

因为该 path 变量存的是地址援用，完结以后递归时，将它退出 res 后，该算法还要进入别的递归分支持续搜寻，还要持续将这个 path 传给别的递归调用，它所指向的内存空间还要持续被操作，所以 res 中的 path 的内容会被扭转，这就不对。
所以要弄一份以后的拷贝，放入 res，这样后续对 path 的操作，就不会影响曾经放入 res 的内容。

作者：xiao_ben_zhu
链接：https://leetcode-cn.com/probl…
起源：力扣（LeetCode）
著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。