1. 题目链接：46. 全排列
2. 题目描述：
给定一个不含重复数字的数组
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中的所有整数 互不相同
3.解法（递归）：
3.1 算法思路：
典型的回溯题目，我们需要在每一个位置上考虑所有的可能情况并且不能出现重复。通过深度优先搜索的方式，不断地枚举每个数在当前位置的可能性，并且回溯到上一个状态，直到枚举完所有的可能性，得到正确的结果
每个数是否可能出现在当前位置，只需要判断这个数在之前是否出现即可。
3.2 递归流程：
- 首先定义一个二维数
ret用来存放所有可能的排列，一个一维数组path用来存放正在构建的排列路径，一个一维数组用check来标记每个元素是否已经被使用过，然后从第一个位置开始进行递归 - 在每个递归的状态中，我们维护一个步数
path，表示当前已经处理了几个数字 - 递归结束条件：当
path等于nums数组的长度时，说明我们已经处理完了所有数字，将当前数组存入结果中 - 在每个递归状态中，枚举所有下标
i，若这个下标未被标记，则使用nums数组中当前下标的元素：- 将
check[i]标记为true - 数组中第
path个元素被nums[i]覆盖 - 对第
path+1个位置进行递归 - 将
check[i]重新赋值为flase，表示回溯
- 将
- 最后，返回
ret
特别地，我们可以不使用标记数组，直接遍历path之后的元素（未被使用），然后将其与需要递归的位置进行交换即可
3.3 C++算法代码：
class Solution {
vector<vector<int>> ret; // 存储所有可能的排列结果
vector<int> path; // 当前正在构建的排列路径
bool check[7]; // 标记数组，用于记录每个元素是否已经被使用过
public:
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums); // 调用深度优先搜索函数进行全排列
return ret; // 返回所有可能的排列结果
}
void dfs(vector<int>& nums) {
if (nums.size() == path.size()) { // 如果当前路径的长度等于输入数组的长度，说明已经找到了一个排列
ret.push_back(path); // 将当前路径添加到结果中
return; // 结束当前递归分支
}
for (int i = 0; i < nums.size(); i++) {
if (!check[i]) { // 如果当前元素没有被使用过
path.push_back(nums[i]); // 将当前元素添加到当前路径中
check[i] = true; // 标记当前元素已经被使用过
dfs(nums); // 继续递归搜索下一个元素
// 回溯操作
path.pop_back(); // 移除当前路径中的最后一个元素
check[i] = false; // 标记当前元素未被使用过
}
}
}
};
