LeetCode 热题 100 46. 全排列-EW帮帮网

LeetCode 热题 100 | 46. 全排列

大家好，今天我们来解决一道经典的算法题——全排列。这道题在 LeetCode 上被标记为中等难度，要求给定一个不含重复数字的数组 nums，返回其所有可能的全排列。全排列是排列组合中的经典问题，通常可以通过回溯法来解决。下面我将详细讲解解题思路，并附上 Python 代码实现。

问题描述

给定一个不含重复数字的数组 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]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

解题思路

核心思想

回溯法：
- 回溯法是一种通过递归枚举所有可能解的方法。
- 在生成全排列的过程中，我们逐个选择数组中的数字，并将其加入当前排列中。
- 为了避免重复选择同一个数字，我们需要记录哪些数字已经被使用过。
递归终止条件：
- 当当前排列的长度等于数组的长度时，说明已经生成了一个完整的排列，将其加入结果列表中。
递归过程：
- 遍历数组中的每个数字，如果该数字尚未被使用，则将其加入当前排列，并标记为已使用。
- 递归调用生成下一个数字的排列。
- 在递归返回时，移除当前排列中的最后一个数字，并标记为未使用（回溯）。

Python代码实现

def permute(nums):
    def backtrack(path, used):
        # 如果当前路径的长度等于数组长度，说明已经生成了一个完整的排列
        if len(path) == len(nums):
            result.append(path[:])  # 添加当前排列的副本到结果列表
            return
        
        # 遍历数组中的每个数字
        for i in range(len(nums)):
            if not used[i]:  # 如果当前数字未被使用
                path.append(nums[i])  # 将当前数字加入路径
                used[i] = True  # 标记为已使用
                backtrack(path, used)  # 递归生成下一个数字的排列
                path.pop()  # 回溯：移除当前路径中的最后一个数字
                used[i] = False  # 标记为未使用

    result = []  # 用于存储所有排列
    used = [False] * len(nums)  # 标记数组中的数字是否被使用
    backtrack([], used)  # 开始回溯
    return result

# 测试示例
nums1 = [1, 2, 3]
nums2 = [0, 1]
nums3 = [1]

print(permute(nums1))  # 输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
print(permute(nums2))  # 输出: [[0, 1], [1, 0]]
print(permute(nums3))  # 输出: [[1]]

代码解析

回溯函数 backtrack：
- 参数：
  - path：当前生成的排列。
  - used：布尔数组，标记数组中的每个数字是否已经被使用。
- 递归终止条件：当 path 的长度等于 nums 的长度时，将当前排列加入结果列表。
- 递归过程：遍历数组中的每个数字，如果当前数字未被使用，则将其加入当前排列，并标记为已使用。递归调用生成下一个数字的排列。在递归返回时，移除当前排列中的最后一个数字，并标记为未使用。
结果列表 result：
- 用于存储所有生成的排列。
标记数组 used：
- 用于记录数组中的每个数字是否已经被使用，避免重复选择。

复杂度分析

时间复杂度：O(n!)，其中 n 是数组的长度。生成所有可能的排列需要枚举 n! 种情况。
空间复杂度：O(n)，递归调用栈的深度为 n，同时需要存储当前排列和标记数组。

示例运行

示例 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]]

示例 3

输入：nums = [1]
输出：[[1]]

总结

通过回溯法，我们可以高效地生成数组的所有全排列。这种方法利用递归枚举所有可能的排列，并通过标记数组避免重复选择。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！

LeetCode 热题 100 46. 全排列