I’ve recently been solving some Leetcode problems so decided to share one of them.

**The problem**
Given a string `cats`

, print all its permutations. By permutation means rearrangement of the characters in a given string. The order of characters matters in a permutation.

**Breakdown**

Let’s break the problem into subproblems. How could we re-phrase the problem of getting all permutations for `cats`

in terms of a smaller but similar subproblems?

Let’s assume that our subproblem is **getting all permutations for all the characters except the last one**. It means that we should have permutations for `cat`

. Just for reference here are all 6 possible permutations:

```
cat # 1
cta # 2
atc # 3
act # 4
tac # 5
tca # 6
```

Now our task is simply to put the `s`

character in each possible position for each of the above permutations.

Lets start from the first one - `cat`

. If we place s in all possible positions here is what we’ll get:

```
cat
<s>cat
c<s>at
ca<s>t
cat<s>
```

Correspondingly for second one `cta`

it will look like this:

```
cta
<s>cta
c<s>ta
ct<s>a
cta<s>
```

And so on.

Here is the illustration showing all the permutations of `cats`

.

The problem is that we don’t have a permutation for `cat`

. But we can get it following exactly the same logic. If we need all the permutations for `cat`

, we take all permutations for `ca`

and then put `t`

in each possible position in each of the permutations of `ca`

.

Here is the illustration showing all the permutations of `cat`

.

And once again, we don’t have the permutations of `ca`

, how do we get it? Following the established logic we need to split it. We extract the last character `a`

and place it into all the possible positions of the reminder string `c`

. As `c`

consists of single character we cannot split it further. We reached our **base case**. This is an easy task we can do by placing `a`

in first position and into the last one:

```
ca
ca
ac
```

Here is the illustration showing all the permutations of `ca`

.

Looking at the image below you can see that this is a recursive process.

**Solution**

As shown above we can use recursive approach to solve the problem.

Lets define our function that will be calculating permutations. This function will be called recursively.

```
const getPermutations = (str) => {
const permutations = new Set();
// TODO: add the logic of calculating permutations
return permutations;
};
```

We are using set to make sure that there are no duplicates. It simplifies the code a bit as we don’t need to check if string was present before.

Then we add a handling of the base case. As identified above our base case is a single character. After extracting last character from `ca`

string we were left with `c`

. `c`

is our base case. Once we reached it, there is not much we can do so we simply return this character. To not break function’s signature we return a set with single character.

```
const getPermutations = (str) => {
const permutations = new Set();
// base case
if (str.length <= 1) {
permutations.add(str);
return permutations;
}
// TODO: add the logic of calculating permutations
return permutations;
};
```

If the string contains more than one character we need to split it. We do it by separating the last character.

```
const getPermutations = (str) => {
const permutations = new Set();
// base case
if (str.length <= 1) {
permutations.add(str);
return permutations;
}
const lastChar = str[str.length - 1];
// all the characters except last
const substr = str.slice(0, -1);
// TODO: add the logic of calculating permutations
return permutations;
};
```

Now we need to put the last character into all the possible permutations of the remaining string. For now we don’t have it but lets assume that we do. Just to follow with the process we put a placeholder in a form of an empty set. To put the last character in all the possible positions of available permutations we need to iterate over all of them:

```
const getPermutations = (str) => {
const permutations = new Set();
// base case
if (str.length <= 1) {
permutations.add(str);
return permutations;
}
const lastChar = str[str.length - 1];
// all the characters except last
const substr = str.slice(0, -1);
// TODO: find all possible permutations
// for all chars except last recursively
const partialPermutations = new Set();
// put the last char in all possible positions
// for each of the above permutations
partialPermutations.forEach((permStr) => {
// TODO: generate permutations
});
return permutations;
};
```

Generating a permutation is rather easy. We simply put the character in all the positions.

```
const getPermutations = (str) => {
const permutations = new Set();
// base case
if (str.length <= 1) {
permutations.add(str);
return permutations;
}
const lastChar = str[str.length - 1];
// all the characters except last
const substr = str.slice(0, -1);
// TODO: find all possible permutations
// for all chars except last recursively
const partialPermutations = new Set();
// put the last char in all possible positions
// for each of the above permutations
partialPermutations.forEach((permStr) => {
for (let i = 0; i <= permStr.length; i++) {
const permutation = permStr.slice(0, i) + lastChar + permStr.slice(i);
permutations.add(permutation);
}
});
return permutations;
};
```

And the very last thing we need to do is to find out all the permutations for our string except the last character which is defined as `allCharsExceptLast`

. We can easily do it by calling our function recursively.

```
const getPermutations = (str) => {
const permutations = new Set();
// base case
if (str.length <= 1) {
permutations.add(str);
return permutations;
}
const lastChar = str[str.length - 1];
// all the characters except last
const substr = str.slice(0, -1);
// get all possible permutations
// for all chars except last recursively
const partialPermutations = getPermutations(substr);
// put the last char in all possible positions
// for each of the above permutations
partialPermutations.forEach((permStr) => {
for (let i = 0; i <= permStr.length; i++) {
const permutation = permStr.slice(0, i) + lastChar + permStr.slice(i);
permutations.add(permutation);
}
});
return permutations;
};
```