← 返回完整题库
JavaScript困难

用 JavaScript 实现全排列

参考答案

function permute(arr) {
  const res = [], used = new Array(arr.length).fill(false);
  const dfs = path => {
    if (path.length === arr.length) return res.push([...path]);
    for (let i = 0; i < arr.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(arr[i]);
      dfs(path);
      path.pop(); used[i] = false;
    }
  };
  dfs([]);
  return res;
}

要点:

  • 回溯三部曲:选择 → 递归 → 撤销;
  • 有重复元素时需去重(排序后跳过 i>0 && arr[i]===arr[i-1] && !used[i-1]);
  • 复杂度 O(n!),n 较大时考虑迭代/剪枝;
  • 也可用"交换法"实现(每次与首位交换)。

本题来自 计算机知识面试题库,共 921 道题。