unreasonably effective

class Solution:
    def collect(self, nums, curr, ans):
        if len(curr) == len(nums):
            ans.append( curr[:] )
            return

        for x in nums:
            if x in curr:
                continue

            curr.append(x)
            self.collect(nums, curr, ans)
            curr.pop()

    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        self.collect(nums, [], ans)

        return ans

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # []
        # [1]
        # [2, 1] [1, 2]
        # [3, 2, 1] [2, 3, 1] [2, 1, 3] [3, 1, 2] [1, 3, 2] [1, 2, 3]

        ans = [[]]
        for x in nums:
            tmp = []
            for p in ans:
                m = len(p)
                for i in range(m+1):
                    p2 = p[:]
                    p2.insert(i, x)
                    tmp.append(p2)
            
            ans = tmp
        
        return ans