LC 46全排列Permutations　中等

给定不含重复数字的数组 nums，返回它的所有全排列，顺序不限。

思路 回溯：used 数组标记已选，选→递归→撤销，path 长度达 n 时收集副本。O(n·n!)。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans, path, used = [], [], [False] * n

        def dfs():
            if len(path) == n:
                ans.append(path[:])
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                dfs()
                path.pop()
                used[i] = False

        dfs()
        return ans