题目描述给定一个不含重复数字的数组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 中的所有整数互不相同解题思路全排列问题是回溯算法的经典入门题目核心是穷举所有可能的元素排列顺序。下面我们将详细讲解两种最常用的解法基于 used 数组标记的回溯法和基于原地交换的优化回溯法。方法一回溯法used 数组标记思路分析回溯法的核心思想是 选择 - 递归 - 回溯。对于全排列问题我们需要从数组中依次选择未被使用过的元素加入当前排列路径直到路径长度等于数组长度得到一个完整的排列。然后回溯撤销选择尝试其他可能的元素。具体来说维护一个当前排列path和一个布尔数组usedused[i]表示数组中第 i 个元素是否已被使用遍历数组中的每个元素如果该元素未被使用则将其标记为已使用加入当前排列path递归处理下一个位置递归返回后从path中移除该元素回溯将其标记为未使用当path的长度等于数组长度时将path加入结果集代码实现C#include vector using namespace std; class Solution { private: vectorvectorint result; // 存储所有全排列结果 vectorint path; // 存储当前正在构建的排列 void backtracking(vectorint nums, vectorbool used) { // 终止条件当前排列长度等于数组长度得到一个完整排列 if (path.size() nums.size()) { result.push_back(path); return; } // 遍历所有元素选择未被使用的 for (int i 0; i nums.size(); i) { if (used[i]) continue; // 已使用的元素跳过 used[i] true; // 标记为已使用 path.push_back(nums[i]); // 加入当前排列 backtracking(nums, used); // 递归处理下一个位置 path.pop_back(); // 回溯撤销选择 used[i] false; // 取消标记 } } public: vectorvectorint permute(vectorint nums) { result.clear(); path.clear(); vectorbool used(nums.size(), false); backtracking(nums, used); return result; } };复杂度分析时间复杂度\(O(n \times n!)\)。共有 \(n!\) 种不同的全排列每个排列需要 \(O(n)\) 的时间复制到结果集中。空间复杂度\(O(n)\)。递归调用栈的深度为 n同时path数组和used数组的大小均为 n。方法二回溯法原地交换优化思路分析这种方法不需要额外的used数组来标记已使用的元素而是通过交换数组元素的方式将已选择的元素 固定 在当前位置从而避免重复选择。具体来说维护一个起始索引start表示当前正在处理的位置从start开始遍历数组将每个元素与start位置的元素交换相当于选择该元素作为当前位置的元素递归处理下一个位置start 1递归返回后将元素交换回来回溯当start等于数组长度时将当前数组加入结果集代码实现C#include vector #include algorithm // 用于swap函数 using namespace std; class Solution { private: vectorvectorint result; // 存储所有全排列结果 void backtracking(vectorint nums, int start) { // 终止条件处理完所有位置得到一个完整排列 if (start nums.size()) { result.push_back(nums); return; } // 从start开始遍历选择当前位置的元素 for (int i start; i nums.size(); i) { swap(nums[start], nums[i]); // 选择第i个元素作为当前位置的元素 backtracking(nums, start 1); // 递归处理下一个位置 swap(nums[start], nums[i]); // 回溯交换回来 } } public: vectorvectorint permute(vectorint nums) { result.clear(); backtracking(nums, 0); return result; } };复杂度分析时间复杂度\(O(n \times n!)\)。与方法一相同共有 \(n!\) 种排列每个排列需要 \(O(n)\) 时间复制。空间复杂度\(O(n)\)。递归调用栈的深度为 n不需要额外的used数组空间效率略高于方法一。两种方法对比方法优点缺点适用场景used 数组标记法逻辑清晰易于理解不易出错需要额外的布尔数组空间初学者入门面试答题不易写错原地交换法节省空间代码更简洁生成的排列顺序与输入顺序不同逻辑稍抽象追求空间效率熟悉回溯思想后使用总结全排列问题是回溯算法的标杆题目掌握这两种解法对于理解回溯算法的核心思想至关重要。used 数组标记法是最直观的写法通过显式标记已使用的元素逻辑清晰面试时优先推荐使用原地交换法通过交换元素实现标记节省了额外的空间但需要注意交换和回溯的顺序与子集问题不同全排列问题每次都需要遍历所有未使用的元素而不是从某个起始索引开始这是两者最核心的区别