Permutations
你会得到一个由互不相同的整数构成的列表 nums。返回这些值的所有排列，每个排列都是一个恰好使用每个值一次的列表，因此 n 个值会有 n! 种排列。按字典序列出它们：逐个位置比较两个排列，由第一个不同的位置决定顺序。对于 [1, 2, 3]，这会让 [1, 2, 3] 排在最前面，[3, 2, 1] 排在最后面。
函数
- numsinteger-array
- 值各不相同，顺序不限
- 返回值integer-2d-array
- 按字典序排列的所有值顺序
约束条件
1 ≤ nums.length ≤ 6-10 ≤ nums[i] ≤ 10- 在
nums中的所有值都不相同。 nums的顺序可能是任意的。
示例
- 输入
- nums = [3, 1, 2]
- 输出
- [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
- 解释
- 以 1 开头的排列在前，
[1, 2, 3]排在[1, 3, 2]前面，因为在第二个位置上，2 比 3 小。输入顺序无关紧要。
- 输入
- nums = [2, -1]
- 输出
- [[-1, 2], [2, -1]]
- 解释
- 两个值可以按两种顺序排列。
[-1, 2]排在前面，因为 -1 小于 2。
- 输入
- nums = [7]
- 输出
- [[7]]
- 解释
- 一个值只有一种排序方式，也就是列表本身。
进阶
给定一个排列，你能否在原地按字典序生成下一个排列，时间复杂度为 O(n)，额外空间复杂度为 O(1)？
提示
逐个打开提示，每个都会多透露一点。
一次确定一个位置来构建排列。第一个位置可以放多少个值，第二个位置可以放多少个？这能告诉你总数是多少？
记录哪些值已经放置。在每个位置，尝试所有仍可用的值；完成后，再将其设为可用，这样下一次尝试就能从相同的状态开始。
先对值排序，然后编写一个递归辅助函数。如果路径中包含全部
n个值，就记录一份副本。否则，从最小值到最大值遍历这些值，跳过已使用的值，标记一个值为已使用并将其添加到路径中，然后递归调用，接着将其移除并取消标记。优先尝试最小的未使用值，就能让排列自动按顺序生成。
题解
n 个不同的值有 n! 种排列，6 个时为 720，而且你必须全部列出，因此工作量至少为 n × n!。对排序后的值进行回溯，并始终先尝试最小的未使用值，这样就能按字典序生成每种排列，且每种只生成一次。
在每个空隙中插入内容，然后排序
思路
从空列表开始，每次添加一个值，逐步生成所有排列。要把 3 添加到 [1, 2] 中，可以将它插入三个空隙中的任意一个：[3, 1, 2]、[1, 3, 2] 和 [1, 2, 3]。每个由 k+1 个值组成的排列都会恰好生成一次：移除最新添加的值，就能得到生成它的排列，而这个值的位置标明了空隙。
生成排列的顺序并不是排列顺序：对于 [1, 2, 3]，首先生成的是 [3, 2, 1]。因此，最后还要进行排序，需要大约 n! × log(n!) 次比较，每次最多比较 n 个值。对于 6 个值，大约需要读取 720 × 9.5 × 6 ≈ 41,000 次。它还会在内存中保存整整一代排列。
算法
- 先创建一个只包含一个空排列的列表。
- 对于
nums中的每个值，创建一个新列表：对于目前已有的每个排列，以及从 0 到该排列长度的每个插入位置，将插入该值后的排列复制到新列表中。 - 用新列表替换旧列表。
- 按位置对这些排列进行排序，并返回它们。
def permute(nums):
perms = [[]]
for value in nums:
grown = []
for perm in perms:
# Put value into every gap of perm, both ends included.
for gap in range(len(perm) + 1):
grown.append(perm[:gap] + [value] + perm[gap:])
perms = grown
# Insertion order is not lexicographic, so sort at the end.
perms.sort()
return perms使用已访问数组进行回溯
思路
从左到右填入 n 个位置：第一个位置有 n 个候选值，第二个有 n-1 个，以此类推。把它看作一棵树，每条边都会放入一个值，每个深度为 n 的叶节点都代表一种排列。用一个共享的 path 和每个值对应的 used 标记来遍历这棵树：对每个未使用的值，选中它，向下探索一层，然后取消选择。取消选择会恢复到完全相同的状态，因此循环会从同一个节点尝试下一个值。
排列顺序会自然生成。循环会先尝试最小的未使用值，并在更改前缀之前生成所有具有给定前缀的排列，因此 [1, 2, ...] 会排在 [1, 3, ...] 前面，而 [1, 3, ...] 又会排在 [2, ...] 前面。这就是为什么要先对 nums 排序。这棵树大约有 e × n! 个节点，每个节点都会运行一个长度为 n 的循环：时间复杂度为 O(n × n!)。
算法
- 对这些值进行排序，并创建一个包含
n个 false 标记的used数组。 - 编写
explore()。如果path中有n个值，就将其副本追加到结果中，然后返回。 - 否则，对于从 0 到 n-1 的每个索引
i，如果对应的值尚未使用，就将其标记为已使用，并追加values[i]（选择），调用explore()（探索），然后将其移除并标记为未使用（撤销选择）。 - 调用一次
explore()，然后返回结果。
def permute(nums):
values = sorted(nums)
n = len(values)
result = []
path = []
used = [False] * n
def explore():
# A full path is a leaf of the decision tree: one finished ordering.
if len(path) == n:
result.append(path[:])
return
# Smallest unused value first, so the leaves come out in lexicographic order.
for i in range(n):
if used[i]:
continue
used[i] = True
path.append(values[i]) # choose
explore() # explore
path.pop() # un-choose
used[i] = False
explore()
return result
易错点和边界情况
- 记录
path，而不是复制它。所有 n! 个条目最终都会变成同一个列表，遍历结束后这个列表是空的。 - 只撤销一半的选择。如果移除值后仍保留
used[i]的设置，该值就不会出现在后续分支中，最终返回的排列少于 n! 个。 - 没有先对
nums排序。这样排列会按照输入顺序排列，所以[3, 1, 2]会排在最前面。 - 使用交换方法（将
nums[start]与后面的每个位置交换，递归，再换回来），却没有在最后排序。对于[1, 2, 3]，[3, 2, 1]会排在[3, 1, 2]前面。 - 通过搜索
path来判断某个值是否已使用。每次检查需要 n 的时间，而且值重复时会出错；为每个索引设置一个标记则只需 O(1) 时间。
常见问题3
包含 n 个不同元素的列表有多少种排列？
n!，读作 n 的阶乘：第一个位置有 n 种选择，第二个位置有 n-1 种选择，依此类推，最后一个位置有 1 种选择，将它们相乘。3 个值有 6 种排列，6 个值有 720 种排列，而 10 个值就已经有 3,628,800 种排列了，这就是排列问题通常会让 n 保持较小的原因。
生成所有排列的时间复杂度是多少？
O(n × n!)。共有 n! 种排列，写出每一种都需要 n 步，因此当必须返回所有排列时，没有任何方法能做得更好。回溯法达到了这个下界，除此之外，还需要 O(n) 的空间来存储路径、已使用标记和递归信息。
当输入中有重复项时，如何生成排列？
对这些值进行排序，并在每个位置跳过与前一个值相等的值，前提是前一个相同的值尚未使用：i > 0、values[i] == values[i-1] 且 !used[i-1]。这样可以确保相等的值按原有顺序放置，从而每种不同的排列只会生成一次。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def permute(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [3, 1, 2]
预期输出
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]