Step-by-Step Guide to Array Permutation Using Recursion in JavaScript

A guide to solving LeetCode #46: Permutations

If you’re reading this, I reckon that, like me, you were having difficulty solving this LeetCode problem. Or, also like me, you want to lean into understanding recursion better. This is the post for you. We’ll go through my step-by-step solution on how to solve this problem with recursion.

Problem Statement

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]
]

First, I believe it’s a good habit to solve these kinds of problems manually, like a typical person would intuit solving it. And in the process, note the steps you take (i.e. pseudocode). Only then begin translating this to code.

Doing it manually

We get an array with [1, 2, 3]. If I were to get all the permutations of this, and return it in an array of arrays, this would be my process:

1. Take the first element of the array (1), and set it aside.
2. Take the remaining elements (2, and 3) and make one permutation with the original order (1, 2, 3), and another one with the original remaining elements (2 , 3), but swapped (3, 2). So now we have two permutations: [1, 2, 3] and [1, 3, 2].
3. Next, we should go back to that first step, where we took the 1 aside, but go up one element in the array, and set aside the 2.
4. That leaves us with a (1, 3) left. Let’s do the same thing: one permutation with the original order of remaining elements [2, 1, 3], and one with the remaining elements swapped [2, 3, 1]. Now we have four permutations: [1, 2, 3], [1, 3, 2], [2, 1, 3] and [2, 3, 1]
5. Finally, we go up again to step 1, but now with the last element of the array: 3.
6. We take the remaining elements aside (1, 2) and do one permutation with that: [3, 1, 2], and one with the remaining elements swapped [3, 2, 1]. Now we have six permutations: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] and [3, 2, 1]. Because we have no more steps to go in that first part of our exercise, when we go through each element one by one, and leave the remaining elements aside, we return all six of our permutations in the form of an array.

This is our algorithm. Note how we have to keep going back to step 1, going up our array, and doing a swap? That is recursion in action. We’re taking the problem, breaking it down, and repeating it over and over until we’ve iterated through all the steps. Let’s translate this into code.

Coding the Solution

Let’s create a function called permute that takes an array called nums as input. Because we have to return an array of arrays as a result, let’s create an empty array called result to house our results. Let’s go ahead and add a return to this solution at the end as well.

function permute(nums) {
  let result = [];
  return result; 
}

Next, as we’re dealing with recursion, we have to deal with our base case, or when our recursion should stop. There will be two of these:

1. When we don’t have anything left to iterate and/or get an empty input.
2. When we just have one element left: the permutation of anything is itself.

Let’s add that:

function permute(nums) {
  let result = [];
  if (nums.length === 0) return [];
  if (nums.length === 1) return [nums];
  return result; 
}

Next, let’s create a for loop to iterate through the nums array. We’ll also create a variable to house the current number we’re iterating with and call it currentNum.

function permute(nums) {
  let result = [];
  if (nums.length === 0) return [];
  if (nums.length === 1) return [nums];
  for (let i = 0; i < nums.length; i++) {
    const currentNum = nums[i];
  }
  return result;
}

Now the interesting parts begin. We’ve set apart the first number in our iteration, but how do we separate the remaining numbers? Here’s one way:

remainingNums = nums.slice(0, i).concat(nums.slice(i + 1));

What slice does is return a shallow copy of the array. We need a copy because as we’re iterating, we don’t want to modify the input (nums) itself. So with this line of code we’re taking all the numbers, except the one we’re iterating with, and concatenating it together to make another array, and saving it into the variable remainingNums.

(Sidebar: splitting out these remaining numbers, along with returning the right output format at the end, is probably the part I spent most time on trying to get right so don’t sweat it if you have to take some time figuring out what’s going on here. Break down the slice and concat portions and play around with that if you have to).

At this point, we’ve taken one number of the nums element out, split out the remaining numbers. If we look at our steps, our algorithm says that at this point, we did one permutation:

function permute(nums) {
  let result = [];
  if (nums.length === 0) return [];
  if (nums.length === 1) return [nums];
  for (let i = 0; i < nums.length; i++) {
    const currentNum = nums[i];
    const remainingNums = nums.slice(0, i).concat(nums.slice(i + 1));
    const remainingNumsPermuted = permute(remainingNums);
  }
  return result;
}

This might be the simplest, and hardest to comprehend portion of the code: the recursive case.

Here we’re saving into a variable called remainingNumsPermuted the result of running our function again, but only with the remainingNums instead of the complete original nums array.

Now what?

We have to figure out a way to swap our remaining numbers, and return them as an array. But remember: we don’t know how many times we’d have to do this swapping. The remainingNums array might have 2 elements left. It might have 50 elements left. So, we need to iterate through the results of remainingNums(permuted) to make sure we account for all of them:

function permute(nums) {
  let result = [];
if (nums.length === 0) return [];
  if (nums.length === 1) return [nums];
for (let i = 0; i < nums.length; i++) {
    const currentNum = nums[i];
    const remainingNums = nums.slice(0, i).concat(nums.slice(i + 1));
    const remainingNumsPermuted = permute(remainingNums);
  for (let j = 0; j < remainingNumsPermuted.length; j++) {
    }
  }
  return result;
}

Inside of this second for loop, we’ll need to have a permuted array. So let’s create a variable called permutedArray. How do we create a permuted array? Our algorithm said we took the current number we iterated with, and then added the other elements left over to that array. Here’s a way to do that:

permutedArray = [currentNum].concat(remainingNumsPermuted[j])

This takes the current number we’re iterating with (say, 1 in our first step), makes an array out of it, then concatenates the number we’re iterating with in our permutation step.

After this, we push this output in our result array:

(1) function permute(nums) {
(2)  let result = [];
(3)  if (nums.length === 0) return [];
(4)  if (nums.length === 1) return [nums];
(5)  for (let i = 0; i < nums.length; i++) {
(6)    const currentNum = nums[i];
(7)    const remainingNums = nums.slice(0, i).concat(nums.slice(i + (8) 1));
(9)    const remainingNumsPermuted = permute(remainingNums);
(10)   for (let j = 0; j < remainingNumsPermuted.length; j++) {
(11)      const permutedArray =                                     (12) [currentNum].concat(remainingNumsPermuted[j]);
(13)      result.push(permutedArray);
(14)    }
(15)  }
(16)  return result;
(17) }

To some (me included) this can be mind-bending. So let’s walk through this code step-by-step.

Me trying to keep track of all the recursion calls in my head

Code Walk-through

• We start with nums = [1, 2, 3]. This array is clearly larger than 0 or 1 elements, so we skip through the first conditionals and hit the first loop.
• When i = 0, the currentNum = 1 and remainingNum = [2, 3] (lines 6 and 7 of the code)
• Line 9: We initialize a variable called remainingNumsPermuted to house the result of permute([2 ,3]). So let’s see what the result of that is…
• We start back to the top with the recursion, and again, the array is larger than 0 and 1. So we skip those conditionals.
• In this recursion call, when i = 0, currentNum = 2, and remainingNum = [3].
• Again, we initialize a variable called remainingNumsPermuted to house the result of permute([3]). So let’s see what the result of that is…
• We start back to the top with the recursion, but this time, the recursion was called with an array of just one element: 3. So we hit one conditional and return [3] (line 4).
• Now that the second recursion call has an answer, it can take its currentNum of 2, and concatenate that with the result of remainingNumsPermuated[0], which is 3 (line 11).
• Line 13: So now [2, 3] is pushed to result. This recursion call is now complete.
• Line 5: We’re back to the second recursion call, and i is now incremented to 1.
• currentNum = 3, and remainingNums = [2]
• Again, we initialize a variable called remainingNumsPermuted to house the result of permute([2]). And just as when it was called with [3], a [2] is returned to the previous recursion call.
• Now that the second recursion call has an answer from when i = 1, it can take its currentNum of 3, and concatenate that with the result of remainingNumsPermuated[1], which is 2.
• So now [3, 2] is pushed to result. This recursion call is now complete.
• Now the first recursion call has two answers waiting to get resolved: one array [2, 3], and another [3, 2].
• For each one of these, it’s going to take its currentNum (1), concatenate these results (line 10).
• So [1, 2, 3] and [1, 3, 2] get pushed into this recursion call’s results array (line 13).
• Line 5: This recursion call’s i is now incremented to 1, and currentNum = 2.

At this point, the exact same process happens again. This call will ultimately concatenate [1, 3], [3, 1] to 2, and push those results to the results array. And finally, once again when the currentNum = 3, it will concatenate [1 ,2] and [2, 1] to 3.

At the end of that last concatenation, results is returned with [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

It’s a lot…but we got through it!

Let me know if you have any questions in the comments. And remember…

Grit > talent.