全排列-中等

难度：中等

题目描述：
给定一个** 没有重复** 数字的序列，返回其所有可能的全排列。

示例：

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

1
2
3
4
5
6
7
8
9

解题思路：
利用递归的思想，
（1）任意取一个元素放在第一个位置，则有 n 种选择；
（2）再剩下的 n-1 个元素中再取一个元素放在第二个位置则有 n-1 种选择，此时可以看做对 n-1 个元素进行全排列；
（3）重复第二步，直到对最后一个元素进行全排列，即最后一个元素放在最后一个位置，全排列结束

var permute = function (arr) {
  let allArr = [];
  let newArr = [];
  const getArr = (data) => {
    let num;
    data.forEach((item, index) => {
      num = data.splice(index, 1)[0];
      newArr.push(num);
      if (data.length === 0) {
        allArr.push(newArr.slice());
      }
      getArr(data);
      data.splice(index, 0, num); // 为了恢复data
      newArr.pop(); // 为了清空newArr
    });
    return allArr;
  };
  return getArr(arr);
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function backtrack(list, tempList, nums) {
  if (tempList.length === nums.length) return list.push([...tempList]);
  for (let i = 0; i < nums.length; i++) {
    if (tempList.includes(nums[i])) continue;
    tempList.push(nums[i]);
    backtrack(list, tempList, nums);
    tempList.pop();
  }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const list = [];
  backtrack(list, [], nums);
  return list;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

← 子集-中等

# 全排列-中等

全排列-中等