Permutations

https://leetcode.com/problems/permutations/

Question

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

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Answer

Let's build the recursion tree, stole from this video!

We remove 1 from our possible numbers and add it to our array.

Every iteration (i = 0) we iterate over the array.

Now we iterate over [2, 3].

Now we move 2 from our array to the answer set.

Now we push 0.

Our array is now empty, that's our base case. We can return from this function call. But before we do that we want to push this into our answers array.

Something important to note here is our use of the for loop. We use the for loop to insert all the elements from the original set in this way.

Here our for loop goes to 1, and we remove 2 from our loop as that's the 2nd [1] element.

Now we return from the function call as our array is empty and push our answer to our answers list.