JavaScript 全排列算法实现 - 详细解释与代码示例

JavaScript 全排列算法实现 - 详细解释与代码示例

问题: 给定一个数组，例如 nums = [1, 2, 3]，求所有可能的排列组合。

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

代码:

function permute(nums) {
  let result = [];
  const backtrack = (arr) => {
    if (arr.length === nums.length) {
      result.push([...arr]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (arr.includes(nums[i])) {
        continue;
      }
      arr.push(nums[i]);
      backtrack(arr);
      arr.pop();
    }
  };
  backtrack([]);
  return result;
}

console.log(permute([1, 2, 3])); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

解释:

该算法使用回溯法。从空数组开始，每次往数组中添加一个数字，如果该数字已经存在于数组中，则跳过。当数组长度等于原始数组长度时，说明已经找到了一种排列，将其添加到结果数组中。然后继续回溯，将添加的数字弹出，尝试其他数字的排列，最终得到所有可能的排列组合。

算法步骤:

1. 初始化一个空数组 result 来存储所有排列组合。
2. 使用递归函数 backtrack 来实现回溯过程。
3. 在 backtrack 函数中，如果当前数组长度等于原始数组长度，则说明已经找到了一种排列，将其添加到 result 数组中。
4. 遍历原始数组，对于每个数字，判断其是否已经存在于当前数组中。如果存在，则跳过；如果不存在，则将该数字添加到当前数组中，并递归调用 backtrack 函数，继续尝试其他数字的排列。
5. 在 backtrack 函数返回后，将添加的数字弹出，以便尝试其他排列组合。
6. 最终返回 result 数组，包含所有可能的排列组合。

总结:

本文详细介绍了 JavaScript 全排列算法的实现，并结合回溯法的思路进行了解释。希望本文能够帮助您理解全排列算法的实现原理，并能够应用于实际编程中。