class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # Base case: If nums contains only one element, return it wrapped in a list
        if len(nums) == 1:
            return [nums]

        # List to store all permutations
        permutations = []

        # Iterate through the array to fix each element
        for i in range(len(nums)):
            # Extract the current element
            current = nums[i]
            # Remaining elements
            remaining = nums[:i] + nums[i + 1 :]
            # Recursively find permutations of the remaining elements
            for p in self.permute(remaining):
                # Prepend the fixed element and add to the permutations list
                permutations.append([current] + p)

        return permutations