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
