day158—回溯—全排列（LeetCode-46）
题目描述
给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例 1：
输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数互不相同
解决方案：
这段代码的核心功能是生成一个数组的所有全排列（即所有元素的不同排列组合，无重复、无遗漏），采用「按位置填数 + 集合控重 + 回溯」的思路实现，整体逻辑清晰且贴合 C++ 类编程风格。
核心逻辑
成员变量作用：
ans：最终结果数组，存储所有生成的全排列；path：临时路径数组，按位置存储当前正在构造的排列（长度固定为数组长度n）；n：输入数组的长度，标记需要填充的位置总数。
递归函数
dfs逻辑：- 参数说明：
i：表示当前要填充path的第i个位置（从 0 开始）；s：当前可选的数字集合（保证每个位置选的数未被使用过）。
- 终止条件：当
i == n时，说明path的所有位置已填充完毕，此时path是一个完整的排列，将其加入ans后返回； - 核心流程（按位填数 + 集合控重）：① 遍历当前可选集合
s中的所有数字x；② 将x填入path的第i个位置；③ 构造新集合new_s（复制s并删除x），保证下一个位置不会重复选x；④ 递归调用dfs(i+1, new_s)，填充下一个位置；⑤ 无需显式回溯（集合是值传递，新集合不影响原集合，天然实现 “选 / 不选” 的分支隔离）。
- 参数说明：
主函数
permute：- 初始化：记录数组长度
n、调整path长度为n、清空ans避免残留； - 构造初始集合：将输入数组
nums的所有元素存入init_set，作为初始可选数字； - 启动递归：从第 0 个位置开始调用
dfs，最终返回存储所有全排列的ans。
- 初始化：记录数组长度
关键特点
- 控重逻辑：通过
unordered_set的 “选数后删除” 机制，保证每个位置的数字唯一，避免生成重复排列； - 路径管理：
path按位置填充，长度固定为n，无需频繁增删，仅通过赋值更新当前位置的数字； - 集合值传递：
s作为值参数传递，每次递归的集合都是独立拷贝，天然实现回溯（无需手动恢复集合状态）。
总结
- 核心思路：按位置逐个填充数字，用集合控制每个位置选 “未使用过的数字”，递归遍历所有可能的填充组合；
- 关键操作：集合的 “拷贝 + 删除” 是控重核心，
path按位赋值是路径构造核心； - 功能效果：能生成输入数组的所有全排列，无重复、无遗漏，时间复杂度为O(n!)（全排列的最优复杂度）。
以输入nums=[1,2]为例，最终会生成[[1,2],[2,1]]，完全符合全排列的定义。
函数源码：
class Solution { public: // 类内成员变量：保存结果和当前路径 vector<vector<int>> ans={}; vector<int> path={}; int n; // 数组长度 void dfs(int i,unordered_set<int>s){ if (i == n) { // 所有位置填充完毕，保存结果 ans.push_back(path); return; } // 遍历当前可选的所有数字 for (int x : s) { path[i] = x; // 第i个位置填入数字x // 构造新集合：移除已选的x unordered_set<int> new_s = s; new_s.erase(x); dfs(i + 1, new_s); // 递归填充下一个位置 } } vector<vector<int>> permute(vector<int>& nums) { n = nums.size(); path.resize(n); // 初始化路径数组 ans.clear(); // 清空结果（避免多次调用时残留） // 构造初始可选集合：包含nums所有元素 unordered_set<int> init_set(nums.begin(), nums.end()); // 调用辅助函数：从第0个位置开始填充 dfs(0, init_set); return ans; } };