46.Permutations

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # answer perspective（对每个位置枚举一个数）
        # using hash set for efficiency
        ans = []
        path = []
        n = len(nums)
        def dfs(i, s):
            if i == n:
                ans.append(path[:])
                return
            # 和组合相比需要顺序不一样的解
            for j in s:
                path.append(j)
                dfs(i+1, s-{j})
                path.pop()
        dfs(0, set(nums))
        return ans