全排列

问题

给定一个不含重复数字的数组 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 中的所有整数 互不相同

链接：https://leetcode-cn.com/leetbook/read/2021-spring-recruitment/5fku35/

解答

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(nums, len_nums, depth, path, res):
            for i in range(len_nums):
                if depth == len_nums:
                    res.append(path.copy())
                    return
                if not used[i]:
                    used[i] = True
                    path.append(nums[i])
                    dfs(nums, len_nums, depth+1, path, res)
                    used[i] = False
                    path.pop()
        
        if not nums:
            return []
        len_nums = len(nums)
        nums = sorted(nums)
        # 深度depth=0
        depth = 0
        used = [False]*len_nums
        path = []
        res = []

        dfs(nums, len_nums, depth, path, res)

        return res