每天一道leetcode(Day 50)

46. 全排列

题目描述

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

示例

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

解题思路

回溯法，套用模板即可。

本题回溯法的出口是 path 的长度达到了和 nums 的长度一样，意味着路径已走完，一种排列组合已生成，推入 res 数组。

类似题目：
39. 组合总和
47. 全排列 II

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  let res = [],
    len = nums.length,
    path = [];
  function back_track(path) {
    if (path.length === len) {
      res.push(path.slice());
    }
    for (const num of nums) {
      if (path.includes(num)) continue;
      path.push(num);
      back_track(path);
      path.pop();
    }
  }
  back_track(path);
  return res;
};

参考

46. 全排列