Leetcode diary: 1079 - Letter Tile Possibilities

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

This is definitely on the harder of the medium scale question. It asks for all the possible permutation arrangement of a given string.
Below is my code:

numTilePossibilities = function(tiles) {

    const answer = new Set();
    const leftOver = tiles.split('');

    recurr([], leftOver);

    function recurr (currentArray, leftOverArray) {
        leftOverArray.forEach(function(ele, index){
            const newCurrent = currentArray.slice()
            newCurrent.push(ele);    
            answer.add(newCurrent.join(''));
            recurr(newCurrent, leftOverArray.slice(0, index).concat(leftOverArray.slice(index+1)))
        })
    }

    return answer.size;
};

I think my answer is pretty dang intuitive, I'd wager it's the most intuitive. The primary goal is assemble all of the permutations and add it to a set to record the unique combinations.

the intuitive technique is to use recursion somehow since there are ridiculous number of iterations. We would need an array to keep track of the current permutation, so "currentArray". We will also have another array to keep track of the unused elements, hence "leftOverArray".

The next intuitive step is to utilize the for loop on the leftOverArray, since all of the letters has to be used somehow.

Now my logic leap told me that when we go to the next recursion, we are removing the current element from the leftOverArray array and it has to be a copy of the leftOverArray itself for the current recursion. So I elected to use

leftOverArray.slice(0, index).concat(leftOverArray.slice(index+1))

The final step is the tricky part: how do I get all the letters in all the possible positions in all of the current and future combination for all the recursions. This was really scary and overwhelming to me. I felt that I was super close but just couldn't get it out of the tip of my tongue.

However, after like 30+ minutes, I realized that for any of the current iteration, I do not have to put element in all of the possible open position; this was confusing and misleading. I just need to push the element to the currentArray.

For example, ABCDE:
the first recursion will create ["A"], ["B"], ["C"], ["D"], ["E"]. Then the next iteration takes turns putting ["B"], ["C"], ["D"], ["E"] next to A, so ["AB"], ["AC"], ["AD"], ["AE"].

Words are ineffective in describing the process clearly, but hopefully you can go back to the first iteration and see that when B is in the second recursion, we'd get ["BA"], ["CB"], ["DB"], ["EB"]. So with a double recursion, we'd get all the possible combinations for the two-letters.

So what the code does is to put all the letters in the first position. Then for each respective recursion, puts all the letters in the second position minus the one in the first position. Then respectively puts all the letters in the third position except the ones in 1st and 2nd position. For each recursion, we also add to the set to keep track.

So with that realization, I finished my code and passed the submission. The performance was poor and it's mostly unlucky timing that the server is slow or something. The codes that are much faster than mine on record is equally as slow as mine when I submit them right now.

The other solutions have an interesting suggestion that you just need to loop on the leftOverArray if it is sorted and you skip on repeated elements:

var numTilePossibilities = function(tiles) {
    let res = 0;

    function permute(str, opt) {
        res++;

        for(let i = 0; i < opt.length; i++) {
            if(opt[i] === opt[i-1]) continue;
            permute(str + opt[i], opt.slice(0, i) + opt.slice(i+1));
        }
    }
    permute('', [...tiles].sort().join(''));
    return res-1;
};

This is harder for me to understand as it does not require a set and for some reason sorted + skipping repeated accounts for uniqueness. If someone has a good explanation on this, please comment!

A slight side note is that this solution is much faster and a very minor improvement for the code above is that "str" for permute() is unnecessary.

Let me know anything on your mind after reading through this, THANKS!