LeetCodehot 力扣热题100 全排列
这段代码的目的是计算给定整数数组的所有全排列（permutations），并返回一个包含所有排列的二维数组。
思路解析
在这段代码中，采用了 深度优先搜索（DFS） 和 回溯 的方法来生成所有的排列。
关键步骤：
1. 回溯：我们通过交换数组中的元素，将数组的每个元素依次放置到每个位置，生成所有的排列组合。
2. 递归：每次递归处理当前索引位置的元素，继续处理下一个位置，直到递归到数组的末尾，表示完成一个排列。
3. 交换回溯：在每次递归后，通过交换操作还原数组的顺序，避免对后续递归产生影响。
代码解析
class Solution {
public:
vector<vector<int>> ans; // 用于存储所有的排列
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums, 0); // 从数组的第一个位置开始深度优先搜索
return ans; // 返回所有的排列
}
void dfs(vector<int>& nums, int n) {
// 如果当前的索引等于数组的长度，说明已经形成了一个排列
if (n == nums.size()) {
ans.push_back(nums); // 将当前排列加入结果集中
return;
}
// 遍历当前索引位置后的所有元素
for (int i = n; i < nums.size(); i++) {
swap(nums[i], nums[n]); // 将第 i 个元素与第 n 个元素交换
dfs(nums, n + 1); // 递归处理下一个位置
swap(nums[i], nums[n]); // 交换回去，恢复原数组状态（回溯）
}
}
};详细注释
1. vector<vector<int>> ans;：
• 用于存储所有的排列组合。
2. vector<vector<int>> permute(vector<int>& nums)：
• permute 是主函数，接受一个整数数组 nums 作为输入，返回一个包含所有排列的二维数组。
• dfs(nums, 0) 从 nums 的第 0 个位置开始深度优先搜索。
3. void dfs(vector<int>& nums, int n)：
• dfs 是深度优先搜索的核心函数，负责递归生成排列。
• nums 是待排列的数组，n 是当前递归处理的索引位置。
4. if (n == nums.size())：
• 如果当前的索引 n 等于数组的大小，说明已经将所有元素排列完毕，形成了一个有效的排列。
• ans.push_back(nums) 将当前的排列（即 nums 数组的状态）加入结果集 ans。
5. for (int i = n; i < nums.size(); i++)：
• 遍历当前索引 n 之后的每一个元素，通过交换生成不同的排列。
6. swap(nums[i], nums[n]);：
• 交换 nums[i] 和 nums[n]，将 nums[i] 放到当前的位置 n。这样可以生成一个新的排列组合。
7. dfs(nums, n + 1)：
• 递归调用 dfs，将处理下一个位置的元素。即当前元素已放置好，继续处理下一个索引。
8. swap(nums[i], nums[n]);：
• 交换回去，恢复原数组状态，这样可以进行下一轮的排列生成（即回溯）。这是为了确保后续的排列生成不会受到之前交换的影响。
好的，接下来我会详细地继续补充并完成整个 深度优先搜索（DFS） 和 回溯 的运行步骤，直到所有排列都生成完毕。
输入数组：
nums = [1, 2, 3]
运行步骤：
我们通过 DFS 和回溯的方法生成 nums 数组的所有排列。
初始状态：
• 输入：nums = [1, 2, 3]
• ans = []（最终存储所有排列的结果）
第 1 层递归：n = 0 (处理第一个位置)
• 当前节点的起始值是 nums = [1, 2, 3]，n = 0，遍历 i = 0 到 i = 2。
1. 第 1 次交换：swap(nums[0], nums[0])，数组未变，仍为 [1, 2, 3]。
• 递归调用 dfs(nums, 1)，进入处理第二个位置。
第 2 层递归：n = 1 (处理第二个位置)
• 当前节点的起始值是 nums = [1, 2, 3]，n = 1，遍历 i = 1 到 i = 2。
1. 第 1 次交换：swap(nums[1], nums[1])，数组未变，仍为 [1, 2, 3]。
• 递归调用 dfs(nums, 2)，进入处理第三个位置。
第 3 层递归：n = 2 (处理第三个位置)
• 当前节点的起始值是 nums = [1, 2, 3]，n = 2，遍历 i = 2 到 i = 2（只剩下一个位置）。
1. 第 1 次交换：swap(nums[2], nums[2])，数组未变，仍为 [1, 2, 3]。
• 递归调用 dfs(nums, 3)，这时 n == nums.size()，说明当前排列已经完成。
2. 将 [1, 2, 3] 加入到 ans 中。
• ans = [[1, 2, 3]]
回溯：恢复状态
• 交换回去，恢复原数组 [1, 2, 3]。
• 返回到 n = 1，继续处理 i = 2。
2. 第 2 次交换：swap(nums[1], nums[2])，数组变为 [1, 3, 2]。
• 递归调用 dfs(nums, 2)，进入处理第三个位置。
第 3 层递归：n = 2 (处理第三个位置)
• 当前节点的起始值是 nums = [1, 3, 2]，n = 2，遍历 i = 2 到 i = 2（只剩下一个位置）。
1. 第 1 次交换：swap(nums[2], nums[2])，数组未变，仍为 [1, 3, 2]。
• 递归调用 dfs(nums, 3)，这时 n == nums.size()，说明当前排列已经完成。
2. 将 [1, 3, 2] 加入到 ans 中。
• ans = [[1, 2, 3], [1, 3, 2]]
回溯：恢复状态
• 交换回去，恢复原数组 [1, 3, 2]。
• 返回到 n = 1，恢复原数组 [1, 2, 3]。
• 返回到 n = 0，恢复原数组 [1, 2, 3]。
第 2 次交换：n = 0 (处理第一个位置)
3. 第 2 次交换：swap(nums[0], nums[1])，数组变为 [2, 1, 3]。
• 递归调用 dfs(nums, 1)，进入处理第二个位置。
第 2 层递归：n = 1 (处理第二个位置)
• 当前节点的起始值是 nums = [2, 1, 3]，n = 1，遍历 i = 1 到 i = 2。
1. 第 1 次交换：swap(nums[1], nums[1])，数组未变，仍为 [2, 1, 3]。
• 递归调用 dfs(nums, 2)，进入处理第三个位置。
第 3 层递归：n = 2 (处理第三个位置)
• 当前节点的起始值是 nums = [2, 1, 3]，n = 2，遍历 i = 2 到 i = 2（只剩下一个位置）。
1. 第 1 次交换：swap(nums[2], nums[2])，数组未变，仍为 [2, 1, 3]。
• 递归调用 dfs(nums, 3)，这时 n == nums.size()，说明当前排列已经完成。
2. 将 [2, 1, 3] 加入到 ans 中。
• ans = [[1, 2, 3], [1, 3, 2], [2, 1, 3]]
回溯：恢复状态
• 交换回去，恢复原数组 [2, 1, 3]。
• 返回到 n = 2，继续处理 i = 2。
2. 第 2 次交换：swap(nums[1], nums[2])，数组变为 [2, 3, 1]。
• 递归调用 dfs(nums, 2)，进入处理第三个位置。
第 3 层递归：n = 2 (处理第三个位置)
• 当前节点的起始值是 nums = [2, 3, 1]，n = 2，遍历 i = 2 到 i = 2（只剩下一个位置）。
1. 第 1 次交换：swap(nums[2], nums[2])，数组未变，仍为 [2, 3, 1]。
• 递归调用 dfs(nums, 3)，这时 n == nums.size()，说明当前排列已经完成。
2. 将 [2, 3, 1] 加入到 ans 中。
• ans = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]
回溯：恢复状态
• 交换回去，恢复原数组 [2, 3, 1]。
• 返回到 n = 1，恢复原数组 [2, 1, 3]。
• 返回到 n = 0，恢复原数组 [1, 2, 3]。
第 3 次交换：n = 0 (处理第一个位置)
4. 第 3 次交换：swap(nums[0], nums[2])，数组变为 [3, 2, 1]。
• 递归调用 dfs(nums, 1)，进入处理第二个位置。
第 2 层递归：n = 1 (处理第二个位置)
• 当前节点的起始值是 nums = [3, 2, 1]，n = 1，遍历 i = 1 到 i = 2。
1. 第 1 次交换：swap(nums[1], nums[1])，数组未变，仍为 [3, 2, 1]。
• 递归调用 dfs(nums, 2)，进入处理第三个位置。
第 3 层递归：n = 2 (处理第三个位置)
• 当前节点的起始值是 nums = [3, 2, 1]，n = 2，遍历 i = 2 到 i = 2（只剩下一个位置）。
1. 第 1 次交换：swap(nums[2], nums[2])，数组未变，仍为 [3, 2, 1]。
• 递归调用 dfs(nums, 3)，这时 n == nums.size()，说明当前排列已经完成。
2. 将 [3, 2, 1] 加入到 ans 中。
• ans = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1]]
回溯：恢复状态
• 交换回去，恢复原数组 [3, 2, 1]。
• 返回到 n = 2，恢复原数组 [3, 2, 1]。
• 返回到 n = 1，恢复原数组 [3, 2, 1]。
• 返回到 n = 0，恢复原数组 [1, 2, 3]。
最终结果
最终生成的排列 ans 中包含了所有可能的排列：
ans = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
总结
1. DFS 遍历：通过递归逐个处理每个位置，生成所有可能的字符组合。
2. 回溯：通过交换和恢复数组状态，确保生成所有排列。
3. 最终生成了所有的排列，并存储在 ans 中。
这样，我们使用回溯和 DFS 的方法成功计算出了所有的排列，并保存在 ans 数组中。