全排列

这个题解使用了回溯算法。首先定义了一个 backtrack 函数，它接收一个 path 参数表示当前的排列路径。如果 path 的长度等于 nums 的长度，说明找到了一个完整的排列，将其加入结果列表中并返回。否则，遍历 nums 中的每个元素，如果该元素还没有被使用过（即不为 None），就将其加入到 path 中，并将该元素在 nums 中标记为 None 表示已使用。然后递归调用 backtrack 函数，继续搜索下一个位置的元素。当递归返回时，将之前标记为 None 的元素恢复为原来的值，并从 path 中移除，以便尝试其他的排列方式。最后，在主函数中调用 backtrack 函数，并传入一个空的 path，开始搜索所有可能的排列。

时间复杂度: O(n * n!)

空间复杂度: O(n * n!)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrack(path):
            # 如果 path 的长度等于 nums 的长度，说明找到了一个完整的排列
            if len(path) == len(nums):
                result.append(list(path))
                return

            for i in range(len(nums)):
                # 如果当前元素已经被使用过，跳过
                if nums[i] is None:
                    continue
                # 将当前元素加入到 path 中
                path.append(nums[i])
                # 将当前元素在 nums 中标记为已使用
                nums[i] = None
                # 递归调用，继续搜索下一个位置的元素
                backtrack(path)
                # 恢复当前元素在 nums 中的值
                nums[i] = path.pop()

        backtrack([])
        return result