def permute_recursive(nums: list[int]) -> list[list[int]]:
    """Recursive implementation to return all permutations of nums"""
    if len(nums) == 1:
        return [nums]

    ans: list[list[int]] = []
    for index, num in enumerate(nums):
        rest = [num for idx, num in enumerate(nums) if idx != index]
        for perms in permute_recursive(rest):
            ans.append([num, *perms])

    return ans