Recursive function for generating all permutations of an input string — InterviewCake

The problem is borrowed from InterviewCake. Although they did a great job explaining the solution in detail, there aren’t that many visuals.

This post is my attempt to visualize the solution:

Sample I/O

Input: ‘cat’

output: {‘cat’, ‘atc’, ‘act’, ‘tca’, ‘tac’, ‘cta’}

The Pattern:

Let’s start small. With 2 chars only.

Suppose we had ca as input.

Their permutations will be:

ca, ac

Notice that if we separated out the last char a and only had c then we are basically attaching the last char (a) into 2 different positions:

Next, let’s add another char.

Suppose we had cat as input:

Similar as above we separate out the last char t , Now notice we could place t in three different positions:

• cat
• tca
• cta

but then again we also can permute ca

Wait! we just did that in the previous step, when we generated ca and ac

So, we can add the last char: t in three positions of ca and ac

We would get

ca:

• cat