046：全排列
作者：沉默王二
发布时间：2024-09-08T15:34:31.217+0800
二哥逼逼：昨天熬夜看了 TI13，雪碧被 nous 干了个 0:2，直接掉到败者组，感觉好解气啊，就喜欢这种强队被弱队干掉的感觉，然后 XG 的胜者组就能少遇点强队。😄今天继续来学习 LeetCode 的第 46 题，全排列。
题意
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
难度
中等
示例
示例 1：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：nums = [1]
输出：[[1]]
### 分析
题意非常朴素，让我们找出nums的所有排列组合。
那我们就可以用回溯算法来解决，遍历数组的每一个元素，然后尝试生成所有的排列，当生成一个完整的排列时，记录该排列，并退回到上一步，然后继续生成新的排列。
就比如说“123”，我们可以先固定 1，然后递归处理 “23”。把 “123”、“132” 排列完成后，回溯到上一步，固定 2，然后递归处理 “13”，以此类推。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
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 中调试运行一遍，对整个题解的理解会更加深刻。
主要看 path 在整个递归过程中的变化。整个题解的效率还不错。
总结
回溯算法非常适合这种全排列的题目，无非就是做选择、递归、撤销选择。
力扣链接：https://leetcode.cn/problems/permutations/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 6100 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（ 主要是理解贪心算法的底层逻辑）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。