class Solution:
    def permute(self,nums: list[int]) -> list[list[int]]:
        length = len(nums)
        l = [i for i in range(length)]
        permute = []
        s = set()
        def get_permute(l, num, length, s, cur):
            if num == length: 
                permute.append(cur)
                return
            for i in range(length):
                if i not in s:
                    s.add(i)
                    cur.append(i)
                    get_permute(l, num+1, length, s, cur.copy())
                    cur.pop()
                    s.remove(i)
        get_permute(l,0,length, s, cur=[])
        rlt = []
        for li in permute:
            rlt.append([nums[i] for i in li])
        return rlt

sol = Solution()
print(sol.permute([1, 2, 3]))