全排列思路整理

对于有n个数的数组一共有n!种排列。我们的思路是按位置一个一个选数字。第0位可以选n个数第1位只能选剩下没用过的以此类推第n位只能选最后剩下的。填满这n个位置就得到一个排列。以下是实现数组全排列的Python代码采用递归回溯法生成所有可能的排列组合def permute(nums): def backtrack(first0): if first n: output.append(nums[:]) for i in range(first, n): nums[first], nums[i] nums[i], nums[first] backtrack(first 1) nums[first], nums[i] nums[i], nums[first] n len(nums) output [] backtrack() return output代码说明该算法通过交换元素位置来生成排列避免了额外的空间复杂度。递归函数backtrack从第一个位置开始依次将每个元素交换到当前位置然后递归处理后续位置。使用示例nums [1, 2, 3] print(permute(nums))输出结果[ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2] ]复杂度分析时间复杂度为O(n×n!)因为共有n!种排列每种排列需要O(n)时间复制到结果中。空间复杂度为O(n)主要消耗在递归调用栈的深度上。def permute(nums): def backtrack(first0): if first n: output.append(nums[:]) for i in range(first, n): nums[first], nums[i] nums[i], nums[first] backtrack(first 1) nums[first], nums[i] nums[i], nums[first] n len(nums) output [] backtrack() return output