剑指 Offer II 083. 没有重复元素集合的全排列

剑指 Offer II 083. 没有重复元素集合的全排列

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

注意：本题与主站 46 题相同：https://leetcode-cn.com/problems/permutations/

思路

回溯法，用 map 存储 node 对应的 edge，采用回溯及深度优先遍历每一个路径，判断终止节点是否是 n-1 节点，是的话存入结果数组中，最后返回即可。

解答

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const temp = [],
    res = [],
    visited = new Array(nums.length).fill(false);
  const visit = () => {
    if (temp.length === nums.length) {
      res.push(temp.slice());
    }
    for (let i = 0; i < nums.length; i++) {
      if (visited[i]) continue;
      const element = nums[i];
      temp.push(element);
      visited[i] = true;
      visit();
      temp.pop();
      visited[i] = false;
    }
  };
  visit(0);
  return res;
};