Recently, I've been once again applying for jobs and, as you can imagine, I found myself going over programming concepts and coding challenges in order to get ready for technical interviews.

This time I noticed I received coding challenges like those HackerRank tests a lot more than usual. Some were quite straightforward, where you just have to show you know how to handle basic operations with arrays and strings. Others were a bit more complicated, where you have to think about time and space complexity on top of, obviously, coming up with a solution.

One specific test caught my attention and made me remember college times when I was learning about recursion. I remember noticing how things can get overly complicated when you are trying to mentally follow the steps taken in a recursive solution. For that reason, I would always start applying my solution to the smallest possible input and move up from there.

The problem

The question asked to generate all the possible permutations of a string. It suggested a recursive approach to solve the problem and it did not have any time or space complexity limitations. Thus, I was not looking for a solution that would run quickly, but rather one that would show I understand how to recognize and solve recursive problems in an "elegant" way.

To think about a solution for this problem while considering time and space complexity takes a bit more effort than we imagine. This is a problem that grows factorially as the input grows. So for this post, we will focus on the mindset around reasoning about recursive problems.

So, imagine you have a string like "abc" as input. The solution would have to generate an array of strings containing ["abc", "acb", "bac", "bca", "cab", "cba"], which represents all the permutations of the input string.

The solution

The thing here is to think about that problem as a set of smaller problems that can be easier to reason about and the solution for those will give you the solution for the whole problem. With that said, I have to say there is a bit of "magic" to it. I remember my teacher in college saying that you just have to trust that one part of the problem is already solved and you just have to focus on solving one subset of the problem, then magically when you put them together you will have the whole thing solved (though we should all take that with a pinch of salt).

For applying that mindset to this problem we first need to identify what would be a subset of the problem. One possible subset would be generating all the permutations for an input with only one character. In this case the list of permutations would have only one item which would be the whole input.

That is more of a base scenario, but it helps with the next subset we'll consider, which will be more helpful. Consider we have a two characters input, "ab", and assume our function already gives us all the permutations for the input except for the last character. At that point we would have the list ["a"] and would need to think about how to add the remaining character "b" to get to all possible permutations. With that list, it is clear to see that the way to get all permutations for "ab" would be to add "b" to all possible positions in every permutation already generated, in this case at the beginning and end of "a". Thus, we'd end up with ["ba", "ab"].

Let's go over one more example while following that same idea, now with the three characters string "abc". Consider our function "magically" gives us the list ["ab", "ba"], which represents all the permutations for "ab". Now in order to get all permutations for the whole input we just need to add the remaining character to every position possible in all permutations already generated. That gives us the list ["cab", "acb", "abc", "cba", "bca", "bac"].

Organizing that in two simple steps we have:

1. Identify a subset of the problem (things like one character, number or item remaining);
2. Figure how to process that remaining item to get the final solution, considering you already have the problem solved for the other items.

The pseudo-code

function generateAllPermutations (input) {
    if (input has only one character) {
      return the input because that already represents all the possible permutations
    } else {
      allPermutations = generateAllPermutations(input without the last character)
      
      for each permutation in allPermutations {
        for each position in permutation {
          add last character to that position
          add final value to list of possible permutations
        }
      }

      return list of possible permutations
    }
}

The JavaScript code

function generateAllPermutations(input) {
  // check for base case, so the recursion won't run for more times than it should
  if (input.length <= 1) {
    return new Set([input]);
  }
  
  // set up variables for the subset we will solve
  const inputWithoutLastChar = input.slice(0, -1);
  const lastChar = input[input.length - 1];
  
  // "magically" get all permutations for part of the input
  const permutationsOfAllCharsExceptLast = generateAllPermutations(inputWithoutLastChar);
  const allPermutations = new Set();
  
  // add remaining char to all permutations in every possible position
  permutationsOfAllCharsExceptLast.forEach(p => {
    for (let i = 0; i <= inputWithoutLastChar.length; i++) {
      allPermutations.add(`${p.slice(0, i)}${lastChar}${p.slice(i)}`);
    }
  })

  return allPermutations;
}

Bonus problem

Just in case there is any chance you are having trouble grasping this, here's a bonus problem, much simpler, for us to look at.

For this, you are asked to recursively calculate the sum of all integers in a list. So if the input is something like [1, 2, 3, 4, 5] your solution must return 15.

Without looking at the answer below, can you follow the steps described above and come up with a solution?

.
.
.
.
.
.
.
.

So, assuming you've tried to come up with a solution, here is a JavaScript version of a possible recursive solution for you to compare.

const sumAll = (input) => {
  // check for base case
  if (!input.length) {
    return 0;
  }
  
  // set up variables for the subset we will solve
  const allNumbersExceptLast = input.slice(0, -1);
  const lastNumber = input[input.length - 1];
  
  // "magically" get sum for pat of the input
  const partialSum = sumAll(allNumbersExceptLast);
  
  // get total sum by adding the remaining number
  return partialSum + lastNumber;
}

With that, I hope solving recursive problems has become a bit easier for you. As with many things, it takes practice to take those steps and apply to bigger problems because sometimes it is not that easy to spot patterns like that. Once you are able to easily identify those patterns you'll be able to solve recursive problems much faster.