Permutations

The idea of the solution is to mimic the way we compute the number of possible permutations without repetition ie n chooses k or (n k): the first value can be chosen among all the elements, the second value can be choosen among all the elements except the first element, ..., and the last value is the remaining element.

Hence for each index:

1) The element is chosen among all the remaining possible elements

2) The function then calls itself (recursion) to choose the next value with the current choosed element removed from the remaining possible element

def permute(nums: List[int]) -> List[List[int]]:
    idx = set([i for i in range(len(nums))])

    # recursion function
    def helper(idx_used):
        # remaining idx to place
        idx_to_place = idx - idx_used

        out = [] # list of all combinations for current + next indexes
        
        # try all elements that remain to place for this index value
        for j in idx_to_place:
            tmp = helper(idx_used | {j}) # for next index call the function with the updated remaining elements
            out.extend([[nums[j]] + l for l in tmp]) # add the combinations of current index j and next indexes
        
        # return the list of combination (list of list) if out is empty return [[]] as a list of list is expected
        return(out if out else [[]])

    return(helper(set()))