Given a collection of distinct integers, return all possible permutations.

What python does

import itertools
return list(itertools.permutations(nums))

and in the documentation, permutation roughly looks like this:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

The python way seems fun. It uses yield and this should speed things up when the iteration can be HUGE.

My way of doing it

If the numbers are all unique

If the numbers are all unique, we will use DFS to generate all permutation. We could find all possible permutations by swapping elements.
At each level i, we will find the number for position i by switching nums[i] with elements that come after it. For example, permute(1,2,3)
will be [1] + permute(2,3) + [2] + permute(1,3) + [3] + permute (2,1). This is directly to the nature of the permutation; We can select 1 element out of all n elements for the first position, that’s why we will spawn three permutes for permute(1,2,3). And the next index can choose from n – 1. That is why we have only 2 numbers in each permute.

One permutation is found when the number to choose from becomes 0.

def permute(nums):
    """
    nums has unique numbers. permute them using DFS
    """
        res = []
        dfs(nums, [], res)
        return res

    def dfs(nums, path, res):
        """
        run dfs and append path when no possible options
        in each iteration of for loop, we will choose nums[i]
        to be the len(path) th element the permutation.
        Eg: at the beginning, path = [], i = 0, nums = [1,2,3]
        the first dfs recursive call will be [1] + permute(2,3)
        the second dfs will be [2] + permute(1,3)
        """
        if not nums:
            res.append(path)

        else:
            for i in range(nums):
                dfs(nums[:i] + nums[i + 1:], path + [nums[i]], res)

What if this the number to be permuted has duplicates?

An example will be [1,2,3,1].
We observe where the duplicate might come from. At first level, we have
[1] + permute(2,3,1), [2] + permute(1,3,1), [3] + permute(1,2,1) , [1] + permute[2,3,1]
We noticed that the last permutation is a duplicate because it choose the same number to be the chosen number at level 1.
So we should keep track of what we have chosen to be the fixed number at each level and don’t recurse on dfs.
The fix would be to add a dictionary at each level of recursion and in the for loop we recurse only if the nums[i] has not been used as the first element at this level.

def dfs(nums, path, res):

    if not nums:
        res.append(path)
    else:

            used_dict = {}
            for i in range(nums):
                        if nums[i] not in used_dict:
                            used_dict[nums[i]] = 1
                dfs(nums[:i] + nums[i + 1:], path + [nums[i]], res)