数组全排列

题目

数组全排列

输入： arr = [1,2,3]; 预期结果：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

实现

var permuteUnique = function (nums) {
  const ans = [];
  const vis = new Array(nums.length).fill(false);
  /**
   * 
   * @param idx 
   * @param perm 
   * @returns 
   */
  const backtrack = (idx, perm) => {
    // 到最后一个数字了，返回结果
    if (idx === nums.length) {
      ans.push(perm.slice());
      return;
    }
    // 循环
    for (let i = 0; i < nums.length; ++i) {
      // 如果数字已选择，且过滤重复数字
      if (vis[i] || (i > 0 && nums[i] === nums[i - 1] && !vis[i - 1])) {
        continue;
      }
      // 选择数字
      perm.push(nums[i]);
      // 将这个位置标记已选择
      vis[i] = true;
      // 递归选择下一个数字
      backtrack(idx + 1, perm);
      // 回溯回来，重置，进行下一个数字的选择
      vis[i] = false;
      perm.pop();
    }
  }
  // 先进行排序
  nums.sort((x, y) => x - y);
  backtrack(0, []);
  return ans;
};