小白真能看一篇文章就学会全排列算法吗？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了小白真能看一篇文章就学会全排列算法吗？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3685字，纯文字阅读大概需要6分钟。

内容图文

片
今天是小浩算法 “365刷题计划” 第97天 。为大家分享如何用算法来求全排列！话不多说，直接看题！

01

PART

全排列是啥

---

什么是全排列？从 n 个不同元素中任取 m（m≤n）个元素，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一个排列。当 m=n 时所有的排列情况叫全排列。

---

比如 [1,2,3] 全排列共有 6 种：

02

PART

全排列题目

---

然后把上面的全排列稍微改改，就变成了一道算法题。。。

---

全排列问题：给定一个 没有重复 数字的序列，返回其所有可能的全排列。

---

示例:

输入: [1,2,3]

输出:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

---

03

PART

题解分析

---

这种由基础数学知识改编而成的题目，在面试时还是很受欢迎的。因为作为面试官，可以用这种题目，来显示自己的博学。（谬论）

---

假如我们不是做算法题，而是做数学题。我们会一个位置一个位置的来考虑，先写出以1开头的排列，再写出以2开头的排列，最后写出以3开头的排列。

这种思路是不是很像深度优先（DFS）的求解过程呢？
1、我们先选择 1，然后为 1 的第二位选择 2，此时 1 的 第三位只能选择 3。

2、然后完成了上面的步骤，我们需要回退到 1，因为只有 1 这里还存在别的选择 1-3，然后填写 1-3 后，只有 1-3-2 一种选择。

3、此时我们需要从 1-3-2，回退到 1-3，再回退到 1，再回退到 根节点，然后重新选择 2。

4、后面的流程相似，我就不一步步的描述了。

当然，如果不省略其回溯过程，就是下面这个样子：

点我看视频

上面分析是分析完了，但是仍然不妨碍你继续懵逼。。。“题目中不是给我的是一个数组吗？作为一个合格的算法小白，我特么根本就不知道 DFS 在这里面咋用啊！！”本来想扔完代码就走，想了想还是决定讲一下。

我们把代码先丢出来（注意，这个代码不是最优的，这样写只是易于大家理解。比如我们还可以通过置换的方式来进行优化，又或者其他的优化方法。但是都大同小异，核心是回溯的过程）：

 1//JAVA
 2class Solution {
 3    List<List<Integer>> ans = new ArrayList<>();
 4
 5    public List<List<Integer>> permute(int[] nums) {
 6        dfs(nums, new ArrayList<>());
 7        return ans;
 8    }
 9
10    private void dfs(int[] nums, List<Integer> tmp) {
11        System.out.println(Arrays.toString(nums) + "," + tmp);
12        if (tmp.size() == nums.length) {
13            ans.add(new ArrayList<>(tmp));
14        } else {
15            for (int num : nums) {
16                if (!tmp.contains(num)) {
17                    tmp.add(num);
18                    dfs(nums, tmp);
19                    tmp.remove(tmp.size() - 1);
20                }
21            }
22        }
23    }
24
25}

假若 nums 为 [1,2,3]，会有下面的输出：

其实这个代码还是很容易理解的，他干了个啥事？就是当我们按顺序去枚举每一位时，我们要把已经选择过的数字排除掉（第16行代码），比如我们上面选择三个数字：

• 在枚举第一位的时候，就有三种情况

• 在枚举第二位的时候，就只有两种情况（前面已经出现的一个数字不可以再出现）

• 在枚举第三位的时候，就只有一种情况（前面已经出现的两个数字不可以再出现）

整个代码其实就干了这么一件事！而 第12行 的代码，其实就是说当枚举到最后一位的时候，这个就是我们要的排列结果，所以我们要放入到全排列结果集中。

那这里还有一个很重要的代码，其实是 第19行，这一步其实是干啥！说白了就是在回到上一位时，我们要就把上一次的选择结果撤销掉。不然如果你之前选过了，后面不就不能继续用了么。

---

郑重申明（读我的文章必看）：

• 本系列所有教程都不会用到复杂的语言特性，大家无须担心没有学过相关语法，算法思想才是最重要的！

• 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode进行过测试运行。

---

04

PART

啰嗦一下

---

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

---

这是最简单的一道全排列题目，注意我在上面的题解中，并没有引入什么状态、路径、选择列表、结束条件之类的专业术语，甚至我连回溯的概念都没有提及。

之所以这样讲，我是希望咱可以从最简单的人类思考出发，而不是去套用一些框架之类的东东。。。。当然，至于更多的概念和回溯框架的东西，我会在后面更为复杂的题目中为大家引入。

内容总结

以上是互联网集市为您收集整理的小白真能看一篇文章就学会全排列算法吗？全部内容，希望文章能够帮你解决小白真能看一篇文章就学会全排列算法吗？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---