京公网安备11010502063487号给定一个元素互不相同的数组，返回它的所有排列，顺序不限。这是回溯最经典的一题：每一层从还没用过的元素里选一个放进当前路径，路径长度达到数组长度就收集一份，返回时把这一步撤销。这道题的结果个数就是 n!，所以耗时主要由结果规模决定，而不是算法细节。本文用真实运行展示回溯里最常见的一个错误（收集路径时忘了复制），实测排列个数和耗时随 n 的增长，给出五种语言的实现，并把回溯过程做成分步演示。
完整题目见官方页面（链接在文末）。数组里的元素互不相同。排列的输出顺序不作要求，核对时按集合比较。基准解是 Python 标准库的 itertools.permutations，与手写回溯是两种独立的实现。一共 12 组用例，覆盖：官方示例、单个元素、两个元素、含负数、长度 4 到 6：
输入 [[1,2,3]] 输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 输入 [[0,1]] 输出 [[0,1],[1,0]] 输入 [[1]] 输出 [[1]] 输入 [[1,2]] 输出 [[1,2],[2,1]] 输入 [[3,2,1]] 输出 [[3,2,1],[3,1,2],[2,3,1],[2,1,3],[1,3,2],[1,2,3]] 输入 [[-1,0,1]] 输出 [[-1,0,1],[-1,1,0],[0,-1,1],[0,1,-1],[1,-1,0],[1,0,-1]]
回溯里的 path 是同一个列表，整个过程只有一个，之后会被不断地添加和删除。收集结果时如果写成 res.append(path)，存进去的是这个列表的引用，而不是当前内容的副本，之后 path 被清空时，之前存的所有"结果"都会一起变成空。下面是真实运行的结果：
[1, 2, 3] 不复制 path 的结果（共 6 个，全部指向同一个列表）：[[], [], [], [], [], []] 正确写法 solve([1, 2, 3])：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
不复制的写法返回了 6 个空列表，个数是对的（6 个），内容全错。这类错误因为个数对得上，在代码里不容易一眼看出来。所以正确写法是 res.append(path[:])（Python）、new ArrayList<>(path)（Java）、append([]int{}, path...)（Go）、[...path]（JavaScript）。C++ 的 push_back(path) 本身会复制一份，所以不需要额外处理。
used[i] 标记第 i 个元素是否已经在路径里。dfs() 里：路径长度等于 n 时收集一份复制；否则依次尝试每个没用过的元素：标记、加入路径、递归、从路径里去掉、取消标记。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums): res, path = [], [] used = [False] * len(nums) def dfs(): if len(path) == len(nums): res.append(path[:]) # 必须复制：path 之后还会被继续修改 return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) dfs() path.pop() # 回溯：撤销这一步选择 used[i] = False dfs() return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,2,3]] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[0,1]] → [[0,1],[1,0]] [[1]] → [[1]] [[1,2]] → [[1,2],[2,1]] [[3,2,1]] → [[3,2,1],[3,1,2],[2,3,1],[2,1,3],[1,3,2],[1,2,3]] [[-1,0,1]] → [[-1,0,1],[-1,1,0],[0,-1,1],[0,1,-1],[1,-1,0],[1,0,-1]]
Java · 解法代码class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); dfs(nums, new boolean[nums.length], new ArrayList<>(), res); return res; } private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) { if (path.size() == nums.length) { res.add(new ArrayList<>(path)); // 必须复制：path 之后还会被继续修改 return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; used[i] = true; path.add(nums[i]); dfs(nums, used, path, res); path.remove(path.size() - 1); // 回溯：撤销这一步选择 used[i] = false; } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,2,3]] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[0,1]] → [[0,1],[1,0]] [[1]] → [[1]] [[1,2]] → [[1,2],[2,1]] [[3,2,1]] → [[3,2,1],[3,1,2],[2,3,1],[2,1,3],[1,3,2],[1,2,3]] [[-1,0,1]] → [[-1,0,1],[-1,1,0],[0,-1,1],[0,1,-1],[1,-1,0],[1,0,-1]]
Go · 解法代码func permute(nums []int) [][]int { res := [][]int{} path := []int{} used := make([]bool, len(nums)) var dfs func() dfs = func() { if len(path) == len(nums) { res = append(res, append([]int{}, path...)) // 必须复制：path 之后还会被继续修改 return } for i := range nums { if used[i] { continue } used[i] = true path = append(path, nums[i]) dfs() path = path[:len(path)-1] // 回溯：撤销这一步选择 used[i] = false } } dfs() return res }
$ go build -o bin . && ./bin < cases.jsonl [[1,2,3]] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[0,1]] → [[0,1],[1,0]] [[1]] → [[1]] [[1,2]] → [[1,2],[2,1]] [[3,2,1]] → [[3,2,1],[3,1,2],[2,3,1],[2,1,3],[1,3,2],[1,2,3]] [[-1,0,1]] → [[-1,0,1],[-1,1,0],[0,-1,1],[0,1,-1],[1,-1,0],[1,0,-1]]
JavaScript · 解法代码function permute(nums) { const res = []; const path = []; const used = new Array(nums.length).fill(false); const dfs = () => { if (path.length === nums.length) { res.push([...path]); // 必须复制：path 之后还会被继续修改 return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; used[i] = true; path.push(nums[i]); dfs(); path.pop(); // 回溯：撤销这一步选择 used[i] = false; } }; dfs(); return res; }
$ node run.js < cases.jsonl [[1,2,3]] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[0,1]] → [[0,1],[1,0]] [[1]] → [[1]] [[1,2]] → [[1,2],[2,1]] [[3,2,1]] → [[3,2,1],[3,1,2],[2,3,1],[2,1,3],[1,3,2],[1,2,3]] [[-1,0,1]] → [[-1,0,1],[-1,1,0],[0,-1,1],[0,1,-1],[1,-1,0],[1,0,-1]]
C++ · 解法代码#include <vector> using namespace std; class Solution { void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) { if (path.size() == nums.size()) { res.push_back(path); // vector 的 push_back 会复制一份 return; } for (int i = 0; i < (int)nums.size(); i++) { if (used[i]) continue; used[i] = true; path.push_back(nums[i]); dfs(nums, used, path, res); path.pop_back(); // 回溯：撤销这一步选择 used[i] = false; } } public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<bool> used(nums.size(), false); vector<int> path; dfs(nums, used, path, res); return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,2,3]] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[0,1]] → [[0,1],[1,0]] [[1]] → [[1]] [[1,2]] → [[1,2],[2,1]] [[3,2,1]] → [[3,2,1],[3,1,2],[2,3,1],[2,1,3],[1,3,2],[1,2,3]] [[-1,0,1]] → [[-1,0,1],[-1,1,0],[0,-1,1],[0,1,-1],[1,-1,0],[1,0,-1]]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
我用同一个解法生成了 n 从 1 到 9 的所有排列，核对个数是否等于 n!，并测量耗时（三次中最快）：
n | 排列个数 | n! | 耗时（三次中最快） 1 | 1 | 1 | 0.00 ms 2 | 2 | 2 | 0.00 ms 3 | 6 | 6 | 0.00 ms 4 | 24 | 24 | 0.01 ms 5 | 120 | 120 | 0.06 ms 6 | 720 | 720 | 0.34 ms 7 | 5040 | 5040 | 2.56 ms 8 | 40320 | 40320 | 22.42 ms 9 | 362880 | 362880 | 243.76 ms
每个 n 的排列个数都严格等于 n!，从 n = 5 到 n = 9 耗时依次是 0.06ms、0.34ms、2.56ms、22.42ms、243.76ms，每增加 1，耗时大约乘以新的 n（约 5.7 倍、7.5 倍、8.8 倍、10.9 倍），与阶乘增长一致。n = 10 就有 362 万个排列，n = 12 有 4.79 亿个，输出本身就放不下，所以这道题的 n 只会到 6。
n 从 5 到 8，手写回溯与 itertools.permutations 的耗时（每个取三次中最快）：
元素个数 n | 暴力解 | 本文解法
5 | 0.011 ms | 0.054 ms
6 | 0.056 ms | 0.338 ms
7 | 0.685 ms | 2.585 ms
8 | 20.835 ms | 22.664 msn = 8 时手写回溯 22.7ms，itertools.permutations（C 实现）20.8ms，差距很小；n 更小时手写的常数较大（n = 5 时 0.054ms 对 0.011ms）。这说明当 n 变大后，耗时主要是输出 n! 个结果所花的，而不是回溯本身的开销。
Python 版本另外和 itertools.permutations 做了随机对拍，元素取自 -10 到 10、互不相同，长度 1 到 6：
随机对拍 2000 组（长度 1 到 6、互不相同的整数（取值 -10 到 10）；结果按集合比较，不要求排列的输出顺序），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 [1, 2, 3]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的排列集合与 solve 的返回值一致。绿色是已经放进路径的元素，蓝色是刚选中的。每次"回溯"帧里，path 少了最后一个元素，对应的元素被标记回未使用，下一个循环就可以选它后面的元素。