pythontip 100days-day24

题目

给定一个没有重复数字的序列，返回其所有可能的全排列。

例子

permute([1,2,3]) -> 
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

假设

1. 输入的数组不为空

tips

1. 回溯算法

答案

解法1

def permute(nums):
    def backtrack(first = 0):
        # 所有数都填完了
        if first == n:  
            res.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)
    res = []
    backtrack()
    return res

性能：

1. 时间复杂度O(n!)
2. 空间复杂度O(n)

关键点：

1. 回溯算法