问题描述：生成n个互异元素a1,a2…an的全排列（所有排列）。

全排列的核心思想是：

确定一个元素： 从待排列的元素中选择一个元素，作为当前排列的第一个元素。
排列剩余元素： 对剩余的元素进行全排列。
组合： 将第一个元素和剩余元素的全排列组合起来，形成一个完整的排列。
重复： 对每个可能的第一个元素重复上述步骤。

const array = ["A", "B", "C", "D", "E"];
function generateFullArrays(arr) {
    if (arr.length === 0) {
        return [[]]; // 一个空数组的全排列是包含一个空数组的数组
    }
    if (arr.length === 1) {
        return [[arr[0]]]; // 只有一个元素，全排列就是包含该元素的数组
    }
    const result = []; // 存储所有生成的全排列
    // 递归情况：遍历数组中的每一个元素，将其作为当前排列的第一个元素
    for (let i = 0; i < arr.length; i++) {
        const currentElement = arr[i]; // 选择当前元素作为第一个元素
 
        // 构建剩余元素数组：除了 currentElement 之外的所有元素
        // 使用 slice() 避免修改原数组
        const remainingElements = arr.slice(0, i).concat(arr.slice(i + 1));
 
        // 递归地生成剩余元素的全排列
        const permutationsOfRemaining = generateFullArrays(remainingElements);
 
        // 将当前元素与剩余元素的全排列进行组合
        for (let j = 0; j < permutationsOfRemaining.length; j++) {
            // 将 currentElement 放在每个剩余元素排列的前面
            result.push([currentElement].concat(permutationsOfRemaining[j]));
        }
    }
    return result;
}

回溯算法实现

 
/* 回溯算法：全排列 I */
function backtrack(state, choices, selected, res) {
    // 当状态长度等于元素数量时，记录解
    if (state.length === choices.length) {
        res.push([...state]);
        return;
    }
    // 遍历所有选择
    choices.forEach((choice, i) => {
        // 剪枝：不允许重复选择元素
        if (!selected[i]) {
            // 尝试：做出选择，更新状态
            selected[i] = true;
            state.push(choice);
            // 进行下一轮选择
            backtrack(state, choices, selected, res);
            // 回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.pop();
        }
    });
}
 
/* 全排列 I */
function permutationsI(nums) {
    const res = [];
    backtrack([], nums, Array(nums.length).fill(false), res);
    return res;
}

全排列与回溯的关系

全排列问题本质上就是一个非常经典的回溯问题。

原因是：

全排列不是一次性直接算出来的，而是要一步一步试。
每一步都要从“还没被选过的元素”里挑一个，放到当前排列后面。
当发现当前路径还没走完，就继续往下递归。
当一条路径走到底，得到一个完整排列，就记录答案。
记录完之后，必须撤销刚才的选择，回到上一个状态，继续尝试别的元素。

而“尝试 → 递归 → 撤销选择 → 再尝试别的分支”这个过程，正是回溯算法的核心。

为什么说全排列“天然适合”回溯

全排列的搜索过程可以想象成一棵树：

第一层：决定第 1 个位置放谁
第二层：决定第 2 个位置放谁
第三层：决定第 3 个位置放谁
…
第 n 层：得到一个完整排列

比如 [1,2,3]：

先选 1，再在剩下的 2,3 里选
再回退
再选 2，再在剩下的 1,3 里选
再回退
再选 3，再在剩下的 1,2 里选

所以，全排列其实就是：

在一棵“选择树”上做深度优先遍历，并且在每次返回上层时撤销当前选择。

这也就是为什么全排列代码看起来往往像 DFS，但更准确地说，它是带撤销操作的 DFS，也就是回溯。

回溯代码里每一部分分别在做什么

看这段代码：

selected[i] = true;
state.push(choice);
 
backtrack(state, choices, selected, res);
 
selected[i] = false;
state.pop();

它刚好对应回溯的四步：

selected[i] = true：标记这个元素已经被选过
state.push(choice)：把当前选择加入路径
backtrack(...)：递归进入下一层
selected[i] = false 和 state.pop()：撤销这次选择，恢复现场

这个“恢复现场”特别重要。

因为如果不恢复：

后面的分支就会继承前一个分支的状态
结果就会错乱

所以回溯和普通递归最大的区别之一，就是：

普通递归更关注“问题如何分解”
回溯更关注“搜索一条路径后，如何退回来继续试别的路”

全排列为什么常被拿来讲回溯

因为它几乎把回溯的几个核心动作都展示全了：

路径 state
选择列表 choices
已选标记 selected
结束条件 state.length === choices.length
做选择
撤销选择

所以很多人学回溯时，第一个标准题就是全排列。

可以把它记成一个模板：

回溯 = 先做选择，递归深入，回来后撤销选择。

而全排列问题，就是这个模板最典型、最标准的应用。

面试版本

全排列问题本质上是一个回溯问题，因为它需要枚举所有可能的排列路径。
每一步从未使用过的元素里选一个加入当前路径，继续递归。
当路径长度等于数组长度时，得到一个完整解。
返回上一层时，要撤销当前选择，这一步就叫“回溯”。
所以全排列其实就是在选择树上做 DFS，并在每次返回时恢复现场。

探索

Akiyama's blog

全排列问题