博客

以下是一个 JavaScript 实现的数组全排列算法：

function permute(nums) {
  let result = [];


  const backtrack = (arr, set) => {
    if (set.size === nums.length) {
      result.push([...set]);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      if (set.has(arr[i])) continue;
      set.add(arr[i]);
      backtrack(arr, set);
      set.delete(arr[i]);
    }
  }


  backtrack(nums, new Set());


  return result;
}


// 示例：
console.log(permute([1, 2, 3]));
// Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

该算法使用了回溯法，即递归地枚举每个元素在当前位置的可能性，并记录已经使用过的元素集合set。当set 中的元素数目等于初始数组的长度时，代表所有元素皆已选取，将set加入到结果数组中。

该算法时间复杂度为O(n! * n)，其中n为数组元素个数，n!为全排列的个数，n为遍历每个排列的时间。

除了递归回溯法外，还有其他方法可以实现数组的全排列，例如使用堆算法。以下是一个 JavaScript 实现的堆算法：

function permute(nums) {
  let result = [];


  const swap = (i, j) => {
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }


  const backtrack = (n) => {
    if (n === 1) {
      result.push([...nums]);
      return;
    }
    for (let i = 0; i < n; i++) {
      backtrack(n - 1);
      if (n % 2 === 0) {
        swap(i, n - 1);
      } else {
        swap(0, n - 1);
      }
    }
  }


  backtrack(nums.length);


  return result;
}


// 示例：
console.log(permute([1, 2, 3]));
// Output: [[1,2,3],[2,1,3],[3,1,2],[1,3,2],[2,3,1],[3,2,1]]

堆算法的思路是固定最后一个元素，对剩余元素做全排列，然后将最后一个元素交换到其他位置，就可以得到所有的排列。该算法的时间复杂度也是O(n! * n)。

总结：

回溯法（Backtracking）是一种通过加约束条件来减少搜索量的算法。其基本思想是：在搜索过程中，每进行一步都将当前的状态保存下来。如果当前状态满足要求，则接受这个状态，否则回溯到上一个状态进行重试。这样一步步的尝试过程，通过枚举所有的可能性，最终得到问题的解。

一个经典的应用场景是在求解全排列问题时。回溯法可以从一个全排列的前缀开始，通过不断调整前缀中元素的位置来得到另一个合法的全排列，直到得到所有合法的全排列。

回溯法的时间复杂度一般比较高，因为需要枚举所有可能的状态，并且可能会存在一些无用的状态。但是回溯法可以通过一些优化措施，例如剪枝等，来减少搜索次数和时间复杂度。