**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
- tca
- cta

**ac:**

- act
- tac
- atc

Bam! we have all of our permutations!!

# Visuals

# Implementation (Python3)

It took me quite somet time to wrap my head around reading the descriptive solution on InterviewCake without any visuals. But with proper visuals, it’s easy peasy!

# Key Takeaways:

- Breakdown the problem into its simplest part then solve that. Replicate that for bigger input
- Remember in recursive calls: the stack frames of a function saves that particular state of the function. You can use these stuffs!
- Always draw the recursive calls! Helps understand the different states