Given a list, return all possible permutations of that list.

nums = [1, 2, 3]
[1, 2, 3], [1, 3, 2],
[2, 1, 3], [2, 3, 1],
[3, 1, 2], [3, 2, 1]

For a list of length n, there are n! permutations of the list.


Draw all possible paths as a tree. Notice that we stop when all numbers are exhausted. The number of branches (leaf nodes) is n!.

All possible paths (permutations) as a tree

We want to generate the all possible paths found in the tree.

To do so, we cannot reuse elements.

As we go down the tree, we form the permutation. We stop when we exhausted all elements.

We collect these permutations in a results list and return it.

Solution in Code