定西市网站建设_网站建设公司_小程序网站_seo优化

题目描述

给定一个不含重复数字的数组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] <= 10
• nums中的所有整数互不相同

解决方案：

这段代码的核心功能是生成一个数组的所有全排列（即所有元素的不同排列组合，无重复、无遗漏），采用「按位置填数 + 集合控重 + 回溯」的思路实现，整体逻辑清晰且贴合 C++ 类编程风格。

核心逻辑

1. 成员变量作用：

   • ans：最终结果数组，存储所有生成的全排列；
   • path：临时路径数组，按位置存储当前正在构造的排列（长度固定为数组长度n）；
   • n：输入数组的长度，标记需要填充的位置总数。

2. 递归函数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)，填充下一个位置；⑤ 无需显式回溯（集合是值传递，新集合不影响原集合，天然实现 “选 / 不选” 的分支隔离）。

3. 主函数permute：

   • 初始化：记录数组长度n、调整path长度为n、清空ans避免残留；
   • 构造初始集合：将输入数组nums的所有元素存入init_set，作为初始可选数字；
   • 启动递归：从第 0 个位置开始调用dfs，最终返回存储所有全排列的ans。

关键特点

• 控重逻辑：通过unordered_set的 “选数后删除” 机制，保证每个位置的数字唯一，避免生成重复排列；
• 路径管理：path按位置填充，长度固定为n，无需频繁增删，仅通过赋值更新当前位置的数字；
• 集合值传递：s作为值参数传递，每次递归的集合都是独立拷贝，天然实现回溯（无需手动恢复集合状态）。

总结

1. 核心思路：按位置逐个填充数字，用集合控制每个位置选 “未使用过的数字”，递归遍历所有可能的填充组合；
2. 关键操作：集合的 “拷贝 + 删除” 是控重核心，path按位赋值是路径构造核心；
3. 功能效果：能生成输入数组的所有全排列，无重复、无遗漏，时间复杂度为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; } };