46. 全排列

二哥逼逼：昨天熬夜看了 TI13，

觉

好解

气啊

，就

喜欢

这种

强

队被

弱队

干掉

的感

觉

，

LeetCode 的

第

然

后

46 题

，

全排

列。

雪

碧

被 nous 干

了

个 0:2，直

接

掉到

败者

组

，

?

感

XG 的者就能少遇点

组就今

学

来

天强能 少 遇 点 。

强队。 ? 今 天 继续来 学 习

题意

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返

回答案。

提示：

• 1 <= nums.length <= 6

• -10 <= nums[i] <= 10

• 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]]

分析

题意非常朴素，让我们找出 nums 的所有排列组合。

046.全排列-20240908150449.png

那我们就可以用回溯算法来解决，遍历数组的每一个元素，然后尝试生成所有的排列，当

生成一个完整的排列时，记录该排列，并退回到上一步，然后继续生成新的排列。

就比如说“123”，我们可以先固定 1，然后递归处理 “23”。把 “123”、“132” 排列完成后，

回溯到上一步，固定 2，然后递归处理 “13”，以此类推。

public class Main04601 {

public List<List<Integer>> permute(int[] nums) {

List<List<Integer>> result = new ArrayList<>();

List<Integer> path = new ArrayList<>();

boolean[] used = new boolean[nums.length]; // 标记数字是否被使用

backtrack(nums, result, path, used);

return result;

}

// 回溯算法

private void backtrack(int[] nums, List<List<Integer>> result, List<Integer>

path, boolean[] used) {

// 如果当前排列的长度等于 nums 的长度，则找到一个完整的排列

if (path.size() == nums.length) {

result.add(new ArrayList<>(path)); // 将当前排列加入结果列表

return;

 }

// 遍历每一个数字，尝试将其加入排列

for (int i = 0; i < nums.length; i++) {

// 如果该数字已经使用过，则跳过

if (used[i]) {

continue;

}

// 做选择：选择当前数字

path.add(nums[i]);

used[i] = true;

// 继续递归处理剩余数字的排列

backtrack(nums, result, path, used);

// 撤销选择：回溯

path.remove(path.size() - 1);

used[i] = false;

}

}

public static void main(String[] args) {

Main04601 solution = new Main04601();

int[] nums = {1, 2, 3};

List<List<Integer>> result = solution.permute(nums);

System.out.println(result); // 输出所有全排列

}

}

简单解释一下。

①、主方法 permute 中：

• 初始化结果列表 result，用于存储所有可能的排列。

• 初始化路径列表 path，用于记录当前的排列。

• 使用布尔数组 used 标记某个数字是否被使用。

• 调用回溯算法 backtrack，开始生成排列。

②、回溯算法 backtrack 中：

• 如果当前排列的长度等于 nums 的长度，则找到一个完整的排列，将其加入结果列

表。

• 遍历 nums 中的每一个数字，尝试将其加入排列。

• 如果该数字已经使用过，则跳过。

• 做选择：选择当前数字，将其加入排列，并标记为已使用。

• 继续递归处理剩余数字的排列。

• 撤销选择：回溯，将当前数字从排列中移除，并标记为未使用。

大家可以在 IntelliJ IDEA 中调试运行一遍，对整个题解的理解会更加深刻。

046.全排列-20240908152859.png

主要看 path 在整个递归过程中的变化。整个题解的效率还不错。

046.全排列-20240908152940.png

总结

回溯算法非常适合这种全排列的题目，无非就是做选择、递归、撤销选择。

力扣链接：https://leetcode.cn/problems/permutations/