46. 全排列 | LeetCode算法题解

题目描述

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

示例:

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

思路

递归。
从nums取出一个元素，再将剩余数组全排列，然后每个排列的每个位置都可以插入该元素得到一个新排列，所有新排列的集合即是nums的全排列

解法

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const permute = nums => {
  if (nums.length === 1) return [nums];

  const [fisrt, ...others] = nums;

  const result = [];
  permute(others).forEach(item => {
    for (let i = 0; i <= item.length; i++) {
      const left = item.slice(0, i);
      const right = item.slice(i);
      result.push([...left, fisrt, ...right]);
    }
  });

  return result;
};