**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:

- ca
**t** **t**ca- c
**t**a

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