全排列I、II

46. 全排列

给定一个 没有重复数字的数组nums，返回其所有可能的全排列。 :::info 示例：
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
] :::

思路

方法一：分治

将排列的问题分治为小问题，由小问题递归推断出最后的解。

var permute = function(nums) {
    const len = nums.length;
    if (len === 1) return [nums];
    let res = [];
    for (let i = 0; i < len; i++) {
        // 取出nums[i]
        let num = nums[i];
        // 取出num[i]的数组
        let rest = nums.slice(0,i).concat(nums.slice(i+1, len));
        // 不断递归，直到数组长度为1
        let restPermuteArr =  permute(rest);
        // 合并，加入结果数组
        for (let item of restPermuteArr) {
            res.push(item.concat(num));
        }
    }
    return res;
};

方法二：回溯法

用一个数组used记录当前元素是否被使用过，同时利用一个路径栈path存储路径。
遍历目标数组，将当前元素i存入路径栈path中并标记该元素，即used[i] = true，然后开始递归。当路径栈长度等于目标数组长度时，即说明排列元素已满，加入到结果数组res中。

var permute = function(nums) {
    const len = nums.length;
    const res = [];
    // 定义回溯函数
    const backTracking = (used, path) => {
        if (path.length === len) res.push([...path]);
        for (let i = 0; i < len; i++) {
            // 如果当前元素被使用过，直接跳过本次循环，遍历下一个元素
            if (used[i]) continue; 
            // 将当前元素加入路径栈
            path.push(nums[i])
            // 标记使用过的元素
            used[i] = true;
            backTracking(used, path);
            // 状态重置，撤销之前的操作
            path.pop();
            used[i] = false;
        }
    }
    backTracking([], []);
    return res;
};

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。 :::info 输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
] ::: 本题跟 全排列 的思路一致，只不过需要在一开始排序，然后在回溯过程中增加判断去重：

var permuteUnique = function (nums) {
  const res = [];
  const len = nums.length;
  // 先排序，目的是为了把重复的数字放到一起形成连续，便于后面判断
  nums.sort((a, b) => a - b);
  var backtracking = function (used, path) {
    if (path.length === len) {
      res.push([...path]);
    }
    for (let i = 0; i < len; i++) {
      if (used[i]) continue;
      // 现在假如 第二个数字也是 1，和第一个 1 重复了：
      // 1.首先下标肯定要大于等于 0
      // 2.前后数字相等
      // 3.前面的数字必须标记为 使用过了 
      if (i - 1 >= 0 && nums[i - 1] === nums[i] && !used[i - 1]) continue;
      path.push(nums[i]);
      used[i] = true;
      backtracking(used, path);
      path.pop();
      used[i] = false;
    }
  }
  backtracking([], []);
  return res;
};