面试快结尾了突然来个手写算法题，结果没写出来。

[Exsole]

昨天，远程视频面试。

感觉前面的问题回答得挺好的，突然发了个网址，让我在线写代码。

一个全排列的算法，事后我查了是 leetcode 第 46 道原题，中等难度。

https://leetcode.cn/problems/permutations/

拿到题，最开始想直接数组遍历，逐步迭代，当前全排列基于上一个排列插入新数字的生成新的结果。

结果磕磕绊绊，没写出完整。面试官最后让我说下思路。。。

唉，郁闷了一晚上没睡着。

[optional]

感觉是放水题

[coyoteer]

全排列 dfs 最简单啦

[hankai17]

不刷题的话 应该不好想
如果前面答得好 也没什么

[baislsl]

@Nazz DFS 不重不漏, 已经是最优解法了

[k9982874]

直接递归完事

[dudubaba]

不刷题在面试这种几分钟的紧张氛围里没几人写的出来。

[ccagml]

可惜了，不是出 hard 感觉就是要你了

[JasonLaw]

```python
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def gen_permutations(nums) -> List[List[int]]:
if len(nums) == 1:
return [nums]
permutations = []
for i in range(len(nums)):
for p in gen_permutations(nums[0:i] + nums[i + 1:]):
permutations.append([nums[i]] + p)
return permutations

res = gen_permutations(nums)
return res
```

[JasonLaw]

@JasonLaw #28 https://leetcode.com/problems/permutations/submissions/935632864/

[laowudxf]

没刷过力扣，想了三分钟有了思路，感觉不是很难。

[Tompes]

全排列属于很常规的题了，出这题应该也是想让你过的

[reducm]

LeetCode 46 题的题目描述为：给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

解题思路：

该题可以使用回溯算法来解决，回溯算法解决的问题都可以抽象成树结构，每个节点表示一个状态，每个节点的子节点表示在该状态下可以转移到的所有状态。

在本题中，我们可以将每个元素看作一个节点，然后每个节点的子节点是剩下的元素，表示选择了该元素后可以继续选择哪些元素。因此，我们可以使用回溯算法来遍历这棵树，找到所有的解。

具体实现时，我们可以使用一个数组来保存当前选择的元素，使用一个布尔数组来标记每个元素是否已经被选择过，然后按照如下步骤进行回溯：

如果选择的元素数量等于原始数组的长度，说明已经选择了所有元素，将当前选择的元素列表加入最终结果中。

遍历原始数组，对于每个未被选择过的元素，将其加入选择列表中，并将其标记为已选择，然后递归进入下一层。

回溯时，将选择列表中最后一个元素删除，并将其标记为未选择。

重复上述步骤，直到遍历完所有状态。

Java 代码实现：

class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, new ArrayList<>(), used, res);
return res;
}

private void backtrack(int[] nums, List<Integer> temp, boolean[] used, List<List<Integer>> res) {
if (temp.size() == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!used[i]) {
temp.add(nums[i]);
used[i] = true;
backtrack(nums, temp, used, res);
used[i] = false;
temp.remove(temp.size() - 1);
}
}
}
}

时间复杂度：O(n×n!)，其中 n 表示数组的长度，n! 表示全排列的总数，因为每个全排列包含 n 个元素，因此总共需要枚举 n×n! 个状态。

空间复杂度：O(n)，其中 n 表示数组的长度，空间复杂度取决于递归调用栈的深度和存储当前选择的元素的列表。在最坏情况下，递归调用栈的深度为 n ，因此空间复杂度为 O(n)。

[mqtdut1]

一看就是递归
再看一下，数组长度 1-6 ，那就换总写法吧
写 6 个 if ，2 写 2 层 for ，3 写 3 层 for
https://leetcode.cn/submissions/detail/425663532/

[Nazz]

@mqtdut1 简单粗暴 👍🏻

[gitignore]

递归咯，每个数插在前一个全排列的缝隙里

[0, 1] => [ [ 0, 1 ], [ 1, 0 ] ]

[0 , 1, 2] 相当于在上面每个数组的每个缝隙插入 2:

[0, 1] 插入 2 得到 [2, 0, 1], [0, 2, 1], [0, 1, 2]
[1, 0] 插入 2 得到 [2, 1, 0], [1, 2, 0], [1, 0, 2]

[Exsole]

@gitignore #35
我就是这么思考的。 结果写着写着卡壳了。

[kjstart]

全排列一般用回溯, 找几个经典的题解把常见算法看看就可以了. 从第一位开始全试一遍, 下一层去掉正在使用的数字, 重复上面的步骤.

[littleBink]

我最后面试官给了一道签到题：tom is a cat 倒序输出 cat is a tom 。一看题目以为面试官这是送我 offer ，结果折腾了五分钟，差点没写出来，总是有小细节遗漏了😂

[WashFreshFresh]

@grahamsa0503 好久没刷题确实不熟练，像这个就是有好几种解法。

[JasonLaw]

@grahamsa0503 #38 LeetCode 地址 - https://leetcode.com/problems/reverse-words-in-a-string/description/