Permutations of a String

Subsets asked which items to take. Permutations asks something different: take all of them, and decide what order to put them in. Sounds small, but it moves the problem into a much more expensive part of the world.

How much more expensive

There are n choices for the first position, n - 1 for the second since one item is already used, and so on. That product is n factorial.

n = 3    3 x 2 x 1 = 6 arrangements
n = 5    120
n = 10   3,628,800
n = 13   over 6 billion
n = 20   about 2.4 x 10^18, more than seconds since the universe began

Compare that against subsets. At 20 items, subsets produces about a million answers, which a laptop handles without complaint. Permutations of 20 items produce more arrangements than there have been seconds since the universe began.

The practical takeaway is worth saying plainly. If a problem asks you to enumerate permutations and the input can exceed roughly 10 or 11 items, enumeration isn't the intended solution, and you should be looking for something else entirely. Recognizing that boundary saves you a lot of wasted effort.

The new difficulty: remembering what you used

Subsets kept order out of the way with a start index, and never needed to know which items were already taken, since it only ever looked forward.

Permutations can't do that. Every remaining item is a legal next choice regardless of position, so the loop has to run over all of them, and you need some way to know which are still available.

The direct approach is a parallel array of booleans, one per item, marking whether it's currently placed. Before choosing item i you check the flag; if it's set, that item is already somewhere above you in the current arrangement and can't be used again.

The important detail is in the un-choose step. There are now two pieces of state to undo: the item comes off the arrangement, and its flag goes back to false. Undo one and forget the other, and the search goes wrong in a way that's genuinely hard to read, since the arrangement looks correct while the availability flags no longer match it.

Watch it run

Step through and watch the used flags alongside the arrangement, since every time the recursion returns, both should change together.

The other way, trading clarity for memory

There's a second standard approach, and it avoids the flags entirely.

Think of the array as split at position k: everything before it is decided, everything from k onward is still available. To choose an item for position k, swap it into place, recurse on k + 1, then swap it back.

It uses no extra array, and the un-choose is just the same swap performed again, which is tidy. The cost is that the array gets scrambled during the search, so the items aren't in their original order while you're inside the recursion. If a prune needs to know something about the original ordering, the used-array version is easier to reason about. Both produce the same set of permutations, just occasionally in a different sequence.

When the input has repeats

Everything so far assumed the items are distinct. Give it [1,1,2] and it produces six answers where only three are actually different, since it treats the two 1s as separate objects.

The fix is a small piece of reasoning worth following, since the same pattern turns up in several other problems.

Sort the input first so equal items sit next to each other. Then, among a run of identical items, allow only one fixed order of use: an item may only be placed if the identical item right before it has already been placed. That forces the copies to be used left to right, so each distinct arrangement gets generated exactly once.

items.sort();                     // equal items now sit next to each other

for (let i = 0; i < items.length; i++) {
  if (used[i]) continue;
  // Skip a duplicate unless the copy before it is already placed.
  if (i > 0 && items[i] === items[i - 1] && !used[i - 1]) continue;
  ...
}

The condition reads oddly the first time. It's saying: if this item equals the previous one, and the previous one is not currently in use, we're about to start a duplicate branch a sibling has already handled, so skip it.

The implementation

function permutations(items) {
  const answers = [];
  const current = [];
  const used = new Array(items.length).fill(false);

  function solve() {
    if (current.length === items.length) {
      answers.push([...current]);
      return;
    }

    for (let i = 0; i < items.length; i++) {
      if (used[i]) continue;          // already placed somewhere above

      used[i] = true;                 // choose
      current.push(items[i]);
      solve();                        // explore
      current.pop();                  // un-choose, both halves
      used[i] = false;
    }
  }

  solve();
  return answers;
}

Where it goes wrong

Undoing only half the state. The item gets popped and the flag stays true, or the other way round. The symptom is answers that are too short, or items that vanish from later branches.

Deduplicating without sorting first. The skip rule relies on equal items being adjacent. Unsorted, it removes some duplicates and misses others, which is worse than doing nothing since the output looks nearly right.

Recording the arrangement without copying it. The same bug as in subsets, and it bites harder here, because the working array ends up back in its original order rather than empty, so every stored answer turns out to be the untouched input.

Trying to enumerate permutations of a large input. If n can reach 15, no amount of pruning is going to save an enumeration. The problem wants something else.

Check yourself