LeetCode 46. Permutations 题解题目描述给定一个不含重复数字的数组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]]解题思路这是一个经典的回溯算法问题要求生成一个数组的所有可能的全排列。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解或者至少不是最后一个解回溯算法会通过在上一步进行一些变化来舍弃该解即回溯并且尝试另一种可能。对于全排列问题我们可以使用以下思路选择从剩余的未使用数字中选择一个数字。递归将选择的数字添加到当前排列中然后递归处理剩余的数字。回溯当所有数字都被使用时将当前排列添加到结果中然后回溯到上一步尝试其他可能的选择。代码实现方法一回溯算法def permute(nums): def backtrack(path, used): # 如果路径长度等于数组长度说明找到了一个排列 if len(path) len(nums): result.append(path[:]) return for i in range(len(nums)): # 如果数字已经被使用过跳过 if used[i]: continue # 选择当前数字 path.append(nums[i]) used[i] True # 递归处理剩余数字 backtrack(path, used) # 回溯撤销选择 path.pop() used[i] False result [] backtrack([], [False] * len(nums)) return result方法二交换法另一种实现全排列的方法是使用交换法通过交换数组元素的位置来生成所有排列def permute(nums): def backtrack(start): # 如果已经处理到数组末尾说明找到了一个排列 if start len(nums): result.append(nums[:]) return for i in range(start, len(nums)): # 交换当前位置和 start 位置的元素 nums[start], nums[i] nums[i], nums[start] # 递归处理剩余元素 backtrack(start 1) # 回溯恢复交换 nums[start], nums[i] nums[i], nums[start] result [] backtrack(0) return result复杂度分析时间复杂度O(n!)其中 n 是数组的长度。对于 n 个元素的数组其全排列的数量是 n!因此算法的时间复杂度是 O(n!)。空间复杂度O(n)其中 n 是数组的长度。递归栈的深度最多为 n另外需要额外的空间来存储当前排列和使用状态。算法优化剪枝对于包含重复元素的数组可以通过排序和剪枝来避免生成重复的排列。空间优化可以使用交换法来减少额外空间的使用不需要额外的used数组。测试案例# 测试案例 1 assert permute([1,2,3]) [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] # 测试案例 2 assert permute([0,1]) [[0,1],[1,0]] # 测试案例 3 assert permute([1]) [[1]]总结本题是一个经典的回溯算法问题通过回溯的思想我们可以生成一个数组的所有可能的全排列。回溯算法是一种非常重要的算法思想适用于解决需要枚举所有可能解的问题如组合、排列、子集等。通过本题我们可以更好地理解回溯算法的基本思想通过选择、递归和回溯三个步骤逐步构建解空间当发现当前路径不能得到有效解时回溯到上一步尝试其他可能的选择。这种思想在解决许多算法问题时都非常有用。