用 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 较大时考虑迭代/剪枝;
- 也可用"交换法"实现(每次与首位交换)。