学懂全排列算法

708 阅读3分钟

Leetcode链接

一步步学懂 全排列 算法。

面试被问到全排列

记得之前刚开始学前端的时候还写过全排列,一晃三年过去了,之前怎么写的完全忘记了,说明还是当时没有完全理解全排列算法的精髓,这次好好整理一下。

先从最简单的含有重复数字的全排列写起来

题目里需要输出的结果为

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

我们可以先从可以重复的解法开始,具体来说,我们可以先输出这个结果

[
  [1,1,1],
  [1,1,2],
  [1,1,3],
  [1,2,1],
  [1,2,2],
  [1,2,3],
  [1,3,1],
  [1,3,2],
  [1,3,3],
  [2,1,1],
  [2,1,2],
  [2,1,3],
  [2,2,1],
  [2,2,2],
  [2,2,3],
  [2,3,1],
  [2,3,2],
  [2,3,3],
  [3,1,1],
  [3,1,2],
  [3,1,3],
  [3,2,1],
  [3,2,2],
  [3,2,3],
  [3,3,1],
  [3,3,2],
  [3,3,3]
]

借助辅助图来看一下如何实现上面的结果

代码实现


function all(nums) {
    const len = nums.length;

    // 结果,是一个二维数组
    const res = [];

    // 中间结果
    const curr = [];

    function walk() {
        // 递归首先确定终止条件,当前curr的长度等于nums的长度,表明此次已经收集够3个数了,终止此次递归
        if (curr.length === len) {
            res.push([...curr]);
            return;
        }

        // 否则循环数组
        for (let i = 0; i < len; i++) {

            curr.push(nums[i]);

            walk();

            curr.pop();
        }
    }

    walk();
    return res;
}

进一步改造

function all(nums) {
    const len = nums.length;
    const res = [];
    const curr = [];

    // 记录当前数组是否出现过
    const visited = {};

    function walk() {
        if (curr.length === len) {
            res.push([...curr]);
            return;
        }

        for (let i = 0; i < len; i++) {

            // 如果出现过,继续下一轮循环
            if (visited[nums[i]])  {
                continue;
            }

            // 如果没有出现过,标记当前数字
            curr.push(nums[i]);
            visited[nums[i]] = true;

            // 标记完后,继续下一次递归
            walk();

            // 上一次递归触发终止条件后,会返回到这里
            // 在这里将当前数字从curr中弹出来,并移除标记
            curr.pop();
            visited[nums[i]] = false;
            
        }
    }

    walk();
    return res;
}