Generate all permutations of an input string.

Write a recursive function for generating all permutations of an input string. Return them as a set.

Don’t worry about time or space complexity—if we wanted efficiency we’d write an iterative version.

To start, assume every character in the input string is unique.

Your function can have loops—it just needs to also be recursive.

Read More:

Container with Most Water Interview Question

Most asked Interview Questions

For Example, if you have given input string: ‘abc’ the result should be:

[ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']

This problem can be solved by separating the first letter and find all permutations of the remaining letters. 

So for “abc” we can do:

a bc
a cb
b ac
b ca
c ab
c ba

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 subproblem?

Let’s make our subproblem be getting all permutations for all characters except the last one. If we had all permutations for “cat,” how could we use that to generate all permutations for “cats”?

We could put the “s” in each possible position for each possible permutation of “cat”!

These are our permutations of “cat”:

  cat
cta
atc
act
tac
tca

For each of them, we add “s” in each possible position. So for “cat”:

  cat
    scat
    csat
    cast
    cats

And for “cta”:

  cta
    scta
    csta
    ctsa
    ctas

And so on.

Now that we can break the problem into subproblems, we just need a base case and we have a recursive algorithm!

Now first let’s convert this details into Pseudocode.

permutations(abc) = a + permutations(bc) +
                    b + permutations(ac) +
                    c + permutations(ab)permutations(ab) = a + permutations(b) +
                   b + permutations(a)permutations(a) = a

Now We have enough understanding to convert this Pseudocode into an actual code.

function permutationsTest(inputstring) { 
  let results = []; 
  if (inputstring.length === 1) { 
    results.push(inputstring); 
    return results; 
  } 
  for (let i = 0; i < inputstring.length; i++) { 
    let firstChar = inputstring[i]; 
    let charsLeft = inputstring.substring(0, i) + inputstring.substring(i + 1); 
    let innerPermutations = permutationsTest(charsLeft); 
    for (let j = 0; j < innerPermutations.length; j++) { 
      results.push(firstChar + innerPermutations[j]); 
    } 
  } 
  return results; 
}