一、 问题描述
给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例：
输入：
nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
二、 核心思路：回溯 (Backtracking)
全排列问题是回溯算法最经典的入门题。回溯算法的本质是决策树的深度优先遍历 (DFS)。
我们可以将全排列问题具象化为：有n个空位，我们需要从左到右依次填入nums中的数字。每个数字只能用一次。
1. 状态定义
在遍历决策树的过程中，我们需要维护以下几个关键状态：
路径 (Path)：记录当前已经做出的选择（即当前正在生成的排列）。
选择列表：当前还可以做出的选择（即数组中还未被使用的数字）。
结束条件：到达决策树底层，无法再做选择的条件。
2. 关键难点：如何记录“已使用”？
由于数组中的元素不能重复使用，我们需要一个标记机制。最直接的方法是引入一个布尔数组used：
used[i] == true：表示nums[i]已经在当前路径中被使用。
used[i] == false：表示nums[i]尚未被使用，可以加入当前路径。
3. 回溯过程图解
以nums = [1, 2, 3]为例，决策树的遍历过程如下：
第一层：可以选择 1, 2, 3。
第二层：如果第一层选了 1，第二层只能从 2, 3 中选。
第三层：如果前两层选了 1, 2，第三层只能选 3。
当路径长度达到 3 时，记录当前路径，并撤销上一步选择（回溯），返回上一层尝试其他分支。
三、 代码实现 (C++)
基于上述思路，我们可以写出非常标准的回溯代码模板：
class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> result; vector<int> path; vector<bool> used(nums.size(), false); backtrack(nums, used, path, result); return result; } private: void backtrack(const vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) { // 1. 终止条件：路径长度等于数组长度，说明找到了一个全排列 if (path.size() == nums.size()) { result.push_back(path); return; } // 2. 遍历选择列表 for (int i = 0; i < nums.size(); ++i) { // 排除不合法的选择：当前数字已被使用 if (used[i]) continue; // 3. 做选择 used[i] = true; path.push_back(nums[i]); // 4. 进入下一层决策树 backtrack(nums, used, path, result); // 5. 撤销选择 (回溯核心) path.pop_back(); used[i] = false; } } };四、 复杂度分析
时间复杂度：O(n×n!)
总共有 n! 种全排列。
每种排列需要 O(n) 的时间将其从
path复制到result中。递归树的节点总数约为 e×n!，因此整体时间复杂度为 O(n×n!)。
空间复杂度：O(n)
递归调用栈的深度最大为 n。
used数组和path数组的空间开销均为 O(n)。注意：返回结果
result占用的空间不计入算法的辅助空间复杂度。
五、 拓展与普适化：回溯算法通用模板
全排列问题揭示了回溯算法解决“组合/排列/子集”类问题的通用范式。我们可以将其抽象为以下伪代码模板：
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 新的选择列表) 撤销选择