排列问题的输出规模会随元素数量呈阶乘级增长，因此在Node.js中实现时，重点往往不是“怎么把所有结果打出来”，而是如何控制递归过程、避免无效分支，并在必要时以惰性方式逐个生成。以一个长度为3的数组为例，全排列只有6种，但长度到达8时结果已经有40320种，长度继续增加会迅速触及内存上限。
从决策树理解排列生成
排列本质上可以看作一棵决策树。第一层决定第一个位置放哪个元素，第二层决定第二个位置放哪个元素，依此类推。每个非叶子节点都表示当前已经确定了部分前缀，剩余的未使用元素继续参与后续选择。递归回溯的过程就是深度优先遍历这棵树，当路径长度等于原数组长度时，说明所有位置都已确定，当前路径就是一个完整排列。
这种决策树模型带来的最大好处是，它能非常自然地映射到代码结构上。你只需要维护一个路径容器和一个使用状态容器，在每一层遍历所有候选元素，把未使用的元素放入路径，进入下一层递归，返回后再撤销选择。撤销选择这一步尤其重要，它让兄弟节点能够继续使用同一个状态空间，而不会互相污染。
两种递归实现：选择法与交换法
选择法是最容易理解的一种实现。它额外使用一个布尔数组或用Set来记录哪些元素已经进入当前路径，每次递归扫描全部元素，跳过已使用项。下面是一个标准的选择法示例：
function permute(nums) {
const result = [];
function backtrack(path, used) {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
path.push(nums[i]);
used[i] = true;
backtrack(path, used);
path.pop();
used[i] = false;
}
}
backtrack([], []);
return result;
}
console.log(permute([1, 2, 3]));
这段代码中的path负责保存当前递归路径，used负责标记状态。每次递归到底部时，通过扩展运算符复制一份路径，避免后续回溯操作修改已经加入结果集中的数组。
交换法则是另一个思路。它不需要额外的状态数组，而是直接在原数组上交换元素位置。用start表示当前正在确定的位置，从start开始依次将后面的元素交换到当前位置，然后递归处理start + 1，返回后再次交换恢复原状。这种方法的优点是不需要频繁创建新数组，空间开销更小。
function permuteBySwap(nums) {
const result = [];
function dfs(start) {
if (start === nums.length) {
result.push([...nums]);
return;
}
for (let i = start; i < nums.length; i++) {
[nums[start], nums[i]] = [nums[i], nums[start]];
dfs(start + 1);
[nums[start], nums[i]] = [nums[i], nums[start]];
}
}
dfs(0);
return result;
}
交换法的递归深度与选择法相同，但状态维护更轻。不过它改变了原数组顺序，如果调用方不希望入参数组被修改，需要在进入函数时先做一次浅拷贝。另外，当数组中存在重复元素时，交换法需要额外判断，否则会产生重复排列。
重复元素的剪枝与字典序排列
如果输入是[1, 1, 2]，直接使用上面的选择法会输出6个结果，但其中包含两个完全相同的排列。去重的关键在于先对数组排序，让相同元素聚在一起。然后在每一层递归中，如果当前元素与前一个元素相同，并且前一个元素在当前路径中尚未被使用，就跳过当前分支。
下面这段代码展示了带剪枝的排列生成方式：
function permuteUnique(nums) {
nums.sort((a, b) => a - b);
const result = [];
const used = Array(nums.length).fill(false);
function backtrack(path) {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
path.push(nums[i]);
used[i] = true;
backtrack(path);
path.pop();
used[i] = false;
}
}
backtrack([]);
return result;
}
这里条件i > 0 && nums[i] === nums[i - 1] && !used[i - 1]的含义是：当遇到重复元素时，只允许第一个元素在当前层级被使用，后续相同元素只有在前面相同元素已经被使用的情况下才能继续使用。这样能保证相同元素在排列中的相对顺序固定，从而消除重复。
字典序排列则是一种完全不同的生成方式。它从当前排列出发，反复寻找下一个字典序更大的排列。核心步骤是从右向左找到第一个相邻升序对，再从右侧找到比该位置元素大的最小元素，交换后反转右侧序列。Node.js中可以利用这种方式按顺序输出排列，但需要保证初始数组已经按升序排列。
使用生成器优化内存与Heap算法
当排列数量很大时，一次性把所有结果收集进数组会占用大量内存。Node.js中的生成器函数允许按需返回结果，调用方可以用for...of逐个消费，也可以在得到目标结果后提前终止遍历。这对脚本工具、CLI应用或流式处理场景非常实用。
function* permuteGenerator(nums) {
const used = Array(nums.length).fill(false);
const path = [];
function* backtrack() {
if (path.length === nums.length) {
yield [...path];
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
path.push(nums[i]);
used[i] = true;
yield* backtrack();
path.pop();
used[i] = false;
}
}
yield* backtrack();
}
for (const p of permuteGenerator([1, 2, 3])) {
console.log(p);
}
生成器版本的选择法和普通版本在递归结构上几乎没有差别，只是把result.push替换成了yield。这样即使排列总数非常大，也不会在内存中同时保存所有结果，消费端拿到一个排列后，上一个排列就可以被垃圾回收。
如果追求更少的交换次数，可以采用Heap算法。它不是按字典序生成，但每次只需要交换一次元素，且能生成所有排列。Heap算法适合那些不关心输出顺序、只关心遍历效率的场景。其核心是用一个计数数组记录每个位置的交换进度，交替交换首元素或当前计数位置元素。
function heapPermute(nums) {
const result = [];
const output = nums.slice();
const n = output.length;
const c = new Array(n).fill(0);
result.push(output.slice());
let i = 0;
while (i < n) {
if (c[i] < i) {
if (i % 2 === 0) {
[output[0], output[i]] = [output[i], output[0]];
} else {
[output[c[i]], output[i]] = [output[i], output[c[i]]];
}
result.push(output.slice());
c[i]++;
i = 0;
} else {
c[i] = 0;
i++;
}
}
return result;
}
Heap算法的实现代码比回溯法更紧凑，因为它不再维护路径和已使用状态，只通过计数数组控制元素交换。不过可读性不如回溯法，如果需要在业务代码中维护或调试，通常仍优先选择回溯法。只有在排列生成性能成为瓶颈、且不要求字典序输出时，才考虑替换为Heap算法。
从实际使用角度看，Node.js里实现排列问题并不是单纯背模板，而是需要根据是否有重复元素、是否要求有序、数据规模大小以及消费方式来选择策略。理解递归树、剪枝条件与生成器之间的配合，比记住某一段代码更重要。