6-005-(LeetCode- 46) 全排列
1. 题目
读题
https://leetcode.cn/problems/permutations/description/
LeetCode 46题是一个**全排列**问题，给定一个不含重复数字的数组 nums ，返回其 **所有可能的全排列**。你可以 **按任意顺序** 返回答案。¹³
例如，输入: [1,2,3]，输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]。²⁴
这是一个典型的**回溯算法**问题，需要用一个used数组记录已经选择的元素，每次从头开始搜索，不合适就退回上一步。²⁴
考查点
2. 解法
思路
首先，定义一个result列表来存储最终的结果，一个path列表来存储当前的排列，一个used数组来存储已经使用过的元素。
然后，定义一个递归函数backtracking，它接收四个参数：nums数组，used数组，path列表和result列表。
在递归函数中，首先判断是否满足递归终止条件，即path的大小是否等于nums的大小。如果是，说明找到了一个全排列，就把path的拷贝加入到result中，并返回。
如果不是，就遍历nums数组中的每个元素，如果该元素没有被使用过，就把它加入到path中，并把used数组对应位置设为true，表示已经使用过。然后递归调用backtracking函数，继续搜索下一个位置的元素。在回溯时，要把path的最后一个元素弹出，并把used数组对应位置设为false，表示未使用过。
这样，通过不断地递归和回溯，就可以遍历所有可能的全排列，并把它们存储到result中。
- 定义一个result列表来存储最终的结果，一个path列表来存储当前的排列，一个used数组来存储已经使用过的元素。
- 定义一个递归函数backtracking，它接收四个参数：nums数组，used数组，path列表和result列表。
- 在递归函数中：
- 如果path的大小等于nums的大小，说明找到了一个全排列，就把path的拷贝加入到result中，并返回。
- 否则，遍历nums数组中的每个元素：
- 如果该元素没有被使用过，就把它加入到path中，并把used数组对应位置设为true。
- 然后递归调用backtracking函数，继续搜索下一个位置的元素。
- 在回溯时，要把path的最后一个元素弹出，并把used数组对应位置设为false。
- 返回result列表作为最终答案。
具体实现
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>(); // 存储结果
List<Integer> path = new ArrayList<>(); // 存储当前的排列
boolean[] used = new boolean[nums.length]; // 存储已经使用过的元素
backtracking(nums, used, path, result); // 递归函数
return result;
}
private void backtracking(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {
if (path.size() == nums.length) { // 如果path的大小等于nums的大小，说明找到了一个全排列
result.add(new ArrayList<>(path)); // 加入到result中
return;
}
for (int i = 0; i < nums.length; i++) { // 对于每个元素
if (!used[i]) { // 如果没有使用过
path.add(nums[i]); // 加入到path中
used[i] = true; // 标记为已使用
backtracking(nums, used, path, result); // 递归调用backtracking
path.remove(path.size() - 1); // 回溯时要把path的最后一个元素弹出
used[i] = false; // 标记为未使用
}
}
}
}