LC-全排列

发表于 更新于 分类于

题目描述

全排列

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

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

代码实现

这是一个典型的回溯算法的应用，在这段代码里 temp.pop() 是点睛之笔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  let result = [];

  function backTracking(temp, remain) {
    if (remain.length === 0) {
      result.push(temp.slice());
    }
    for (let i = 0; i < remain.length; i++) {
      temp.push(remain[i]);
      backTracking(temp, [...remain.slice(0, i), ...remain.slice(i + 1)]);
      // backTracking(temp, remain.slice(0, i).concat(remain.slice(i+1)));
      temp.pop();
    }
  }

  backTracking([], nums);
  return result;
};

console.log(permute([1, 2, 3]))
//  [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]