## DEV Community is a community of 636,189 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading... # 8.7 Permutations Without Dups

###### NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

Write a method to compute all permutations of a string of unique characters.

I've approached this one by taking a specific example: finding all permutations of `123`. Permutations are all the possible combinations of elements, so from `123` we need to get the following ones: `123, 132, 213, 231, 312, 321` - 6 in total. Let's say we knew all permutations of a string of `12`, could we then somehow get the permutations of `123`? Sure! See the drawing: We know that permutations of `12` are `12` and `21` - and it looks like we just need to add 3 to every possible position for each of those arrays in order to get out result 🎉(result should be all arrays in the pink circle). The transition from `1` to `12` works in a similar way: to get all permutations of `12` we just need to put `2` in all possible indices in the string of `1` - either before 1 (`21`) or after (`12`).

In Javascript this logic can be reflected by the following code:

``````function getPermutations(str) {
const lastIndex = str.length - 1;
const lastChar = str[lastIndex];
if (lastIndex === 0) { return [str]; }
const prev = getPermutations(str.slice(0, lastIndex));
return prev.flatMap(elem => {
const result = [];
for (let i = 0; i <= lastIndex; i ++) {
const newElem = elem.slice(0, i) + lastChar + elem.slice(i);
result.push(newElem);
}
return result;
});
}
``````

With `getPermutations(str.slice(0, lastIndex))` we're calculating the permutations of a shorter string (string without the last character), and then mapping over the array of these permutations. Each element in the map is then looped over, so that we could create a set of new strings with added last character. This way, for an element `12`, we would be able to return [`312`, `132`, `123`]. Finally, flatMap allows to return the result as one array - `[312, 132, 123, 321, 232, 213]` instead of `[[312, 132, 123], [321, 232, 213]]` - which is convenient for the next iteration of the recursion