题目描述
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以以任意顺序返回答案。
输入格式
- 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]]
方法一：回溯算法
解题步骤
- 初始化：创建一个空列表
res来存储所有排列结果。 - 递归函数：编写一个递归函数，使用当前序列
path和选择列表nums来生成排列。 - 结束条件：如果
path的长度等于nums的长度，则将path添加到结果列表res中。 - 循环选择：遍历
nums中的每个数字，如果数字未被选择，则加入到path，并继续递归，最后撤销选择。
完整代码
def permute(nums):
"""
使用回溯算法生成数组的全排列
:param nums: List[int], 输入的整数数组
:return: List[List[int]], 所有可能的全排列
"""
def backtrack(path, options):
# 如果当前路径的长度等于输入数组的长度，说明找到了一种排列
if len(path) == len(nums):
res.append(path[:])
return
# 遍历当前可选择的数字
for i in range(len(options)):
# 选择当前数字
path.append(options[i])
# 继续递归填下一个数
backtrack(path, options[:i] + options[i+1:])
# 撤销选择
path.pop()
res = []
backtrack([], nums)
return res
# 示例调用
print(permute([1, 2, 3])) # 输出: [[1, 2, 3], [1, 3, 2], ..., [3, 2, 1]]
算法分析
- 时间复杂度：(O(n! \times n))，生成所有排列需要 (n!) 次调用，每次调用处理列表需要 (O(n)) 时间。
- 空间复杂度：(O(n))，递归深度为 (n)，使用了额外的空间存储当前排列。
方法二：字典序生成算法
解题步骤
- 排序：先将数组排序。
- 查找：从右向左查找第一个升序的相邻元素对
(i, j)，即nums[i] < nums[j]。 - 交换与反转：如果找到，再从右向左查找第一个大于
nums[i]的元素nums[k]，交换nums[i]和nums[k]，然后反转i+1到末尾的元素。 - 重复：重复以上步骤直到完全逆序。
完整代码
def permute(nums):
"""
使用字典序算法生成数组的全排列
:param nums: List[int], 输入的整数数组
:return: List[List[int]], 所有可能的全排列
"""
def next_permutation(perm):
# 找到升序的边界
i = len(perm) - 2
while i >= 0 and perm[i] >= perm[i + 1]:
i -= 1
if i == -1:
return False
# 找到需要交换的位置
j = len(perm) - 1 while perm[j] <= perm[i]:
j -= 1
perm[i], perm[j] = perm[j], perm[i]
# 反转i后面的部分
perm[i + 1:] = perm[i + 1:][::-1]
return True
nums.sort()
res = [nums[:]]
while next_permutation(nums):
res.append(nums[:])
return res
# 示例调用
print(permute([1, 2, 3])) # 输出: [[1, 2, 3], [1, 3, 2], ..., [3, 2, 1]]
算法分析
- 时间复杂度：(O(n! ✖️ n))，尽管每次生成下一个排列只需要 (O(n)) 时间，但总共有 (n!) 个排列。
- 空间复杂度：(O(1))，除了输出数组外，空间使用是常数。
方法三：递归交换
解题步骤
- 递归函数定义：定义一个递归函数，使用当前索引
start来处理排列。 - 递归终止条件：如果
start等于数组长度，记录当前排列。 - 递归交换：从
start开始，将每个元素交换到start位置，然后递归处理start + 1。
完整代码
def permute(nums):
"""
使用递归交换方法生成数组的全排列
:param nums: List[int], 输入的整数数组
:return: List[List[int]], 所有可能的全排列
"""
def backtrack(start):
if start == len(nums):
res.append(nums[:])
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
res = []
backtrack(0)
return res
# 示例调用
print(permute([1, 2, 3])) # 输出: [[1, 2, 3], [1, 3, 2], ..., [3, 2, 1]]
算法分析
- 时间复杂度：(O(n! ✖️ n))，需要进行 (n!) 次调用，每次调用中进行的操作与 (n) 成正比。
- 空间复杂度：(O(n))，递归深度最大为 (n)，使用了额外的空间存储当前排列状态。
总结
为了直观地比较解决LeetCode题目46 "全排列"的三种方法，下面的表格将展示它们在不同技术维度的性能和特点，包括时间复杂度、空间复杂度以及各自的优势和劣势。
| 特征 | 方法一：回溯算法 | 方法二：字典序算法 | 方法三：递归交换法 |
|---|---|---|---|
| 时间复杂度 | (O(n! \times n)) | (O(n! \times n)) | (O(n! \times n)) |
| 空间复杂度 | (O(n)) | (O(1)) | (O(n)) |
| 优势 | - 灵活且直观 - 易于实现和理解 | - 非递归，避免栈溢出 - 效率高于普通回溯 | - 实现简单 - 直接在输入数组上操作 |
| 劣势 | - 空间消耗较大 - 深度递归可能导致栈溢出 | - 实现复杂度较高 - 不如回溯直观 | - 多次交换操作复杂 - 递归依旧可能栈溢出 |
| 适用场景 | - 需要所有可能解时 - 教学和基础算法学习 | - 需要按字典顺序生成全排列 - 大规模数据处理 | - 内存使用敏感 - 喜欢简洁代码风格 |
综合分析
方法一（回溯算法）：
- 回溯算法是解决排列、组合问题的经典方法，非常直观，可以灵活地处理各种约束条件。其主要缺点是在深度递归时可能会消耗较多内存，特别是在解空间非常大时。
方法二（字典序算法）：
- 字典序算法提供了一种非递归的解决方案，能够有效地按照字典顺序生成下一个排列，适用于需要顺序输出或者大数据量的问题。然而，这种方法在实现上较为复杂，可能不太直观。
方法三（递归交换法）：
- 递归交换法通过直接在输入数组上进行操作，避免了额外的空间使用，简化了代码的复杂性。但与回溯类似，它的缺点是递归深度大时仍可能导致栈溢出问题，且多次交换操作可能相对复杂。
在选择合适的方法时，可以根据具体问题的需求、可用资源以及开发时间来做决策。例如，对于教学或基础学习，推荐使用回溯算法；对于工业级应用，考虑字典序算法；而对于内存敏感或喜欢简洁代码的场景，递归交换法可能是一个好选择。
