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 数组中。