解题步骤

  1. 有很多分岔路
  2. 这些路里面有死路，也有出路
  3. 通常需要用递归来模拟所有的路

通过回溯的方式实现

  • 时间复杂度：O (n!)

  • 空间复杂度：O (n)

    1. function permute(nums) {
    2.   const res = [];
    4.   const backtrack = (path) => {
    5.       if (path.length === nums.length) {
    6.           res.push(path);
    7.           return;
    8.       }
    10.       nums.forEach((n) => {
    11.           if (path.includes(n)) return;
    13.           backtrack(path.concat(n));
    14.       });
    15.   };
    17.   backtrack([]);
    18.   return res;
    19. }

此处的时间复杂度会比较复杂，因为我们嵌套的过程中有个循环，而循环内又判断了如果包含 n 就不在递归，不能存在重复的元素。所以递归的次数是 n! 代表 n 的阶乘。n! = 123…( n-1)*n 。

由于我们输出的数组是一个临时的变量，所以不能作为空间复杂度的计算对象，代码中没有显示的使用线性增长的变量，但是存在一个递归，而递归的深度就是 n ，所以空间复杂度为 O (n) 。