全排列-46

[sl1673495]

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

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

[1, 2] 可以分割为 1 和 permute([2]) 的所有组合，也可以分割为 2 和 permute([1])的所有组合。

[1, 2, 3] 可以分割为 3 和 permute([1, 2]) 的所有组合（上一步已经求得），也可以分为 2 和 permute([1, 3])的所有组合，以此类推。

let permute = function (nums) {
  let n = nums.length
  if (n === 1) {
    return [nums]
  }

  let res = []
  for (let i = 0; i < n; i++) {
    let use = nums[i]
    let rest = nums.slice(0, i).concat(nums.slice(i + 1, n))
    let restPermuteds = permute(rest)
    for (let restPermuted of restPermuteds) {
      res.push(restPermuted.concat(use))
    }
  }

  return res
}

[vortesnail]

回溯法：

var permute = function (nums) {
  // 保存结果数组，保存每个路径（排列）
  const res = [];
  const len = nums.length;

  // 定义回溯递归函数
  // 传入节点是否被使用过的数组 used 和路径栈 path。
  // used 用来标记节点是否被用过， path 用来存储路径，定义为一个栈
  var backtracking = function (used, path) {
    // 递归出口
    // 如果到达叶子节点，将路径推入结果数组，并返回
    if (path.length === len) {
      res.push([...path]);
    }

    // 遍历候选字符
    for (let i = 0; i < len; i++) {
      // 使用过就下一轮循环
      if (used[i]) continue;

      // undefind 和 fasle 都会进来
      // 这里说明这个数还没有被使用，入栈 path
      path.push(nums[i]);
      // 标记这个数被使用过了
      used[i] = true;
      // 开始进行递归
      backtracking(used, path);
      // 回溯【状态重置】撤销之前的操作
      path.pop();
      used[i] = false;
    }
  }

  // 调用回溯函数，传入参数
  backtracking([], []);
  // 返回结果数组
  return res;
};