46. Permutations

link

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

        s = set()

        def backtrack(current):
            if len(current) == n:
                res.append(current[:])
                return
            
            for i in range(1, n+1):
                if i in s:
                    continue
                s.add(i)
                backtrack(current + [nums[i-1]])
                s.remove(i)

        backtrack([])

        return res