Permutations of a String

Printing every permutation of a string is the standard second backtracking exercise, and it introduces something subsets did not have: a real distinction between a partial state and an answer.

In the subsets tree, every node was an answer. Here only the leaves are. A half-built permutation is not a permutation of anything, so the recording step moves to the bottom of the tree and the internal nodes become pure scaffolding.

Two ways to do it

Both are common enough that you should recognise either on sight.

Step through both

Switch between the two methods below on the same input. The answers match; the order they arrive in does not, and neither does what the array looks like part way down.

In used-array mode, watch the free-characters panel shrink as you descend and refill as you back out. That panel is the boolean array, and it is the entire difference between this and an unconstrained loop.

Then switch to swap mode and watch the array itself change. The swap-back frame after each branch is the un-choose step. Remove it and the array drifts, so the next branch permutes something that was never the input.

When the input has repeats

Give the string AAB to the naive version and it emits six results, of which only three are different. The two As are distinguishable by index and by nothing else, so the algorithm faithfully produces each ordering twice.

Switch the input to AAB above and turn duplicate skipping on. The rejected branches show up in coral: those are the subtrees that would have rebuilt work already done.

The fix depends on which method you are using, and this is the part that catches people who have memorised one of them.

The !used[i-1] half of the first test is the subtle bit. Without it you also block the legitimate case where the previous equal character is already placed higher up the current path, and you lose real answers rather than duplicates.

In code

// Used-array version. Sort first if you want duplicate skipping
// or lexicographic output.
function permutations(str, { dedupe = false } = {}) {
  const chars = dedupe ? [...str].sort() : [...str];
  const used = new Array(chars.length).fill(false);
  const out = [];
  const current = [];

  function backtrack() {
    if (current.length === chars.length) {
      out.push(current.join(""));
      return;
    }

    for (let i = 0; i < chars.length; i++) {
      if (used[i]) continue;
      // Only the leftmost unused copy of a repeated character may go first.
      if (dedupe && i > 0 && chars[i] === chars[i - 1] && !used[i - 1]) continue;

      used[i] = true;
      current.push(chars[i]);      // choose
      backtrack();                 // explore
      current.pop();               // un-choose
      used[i] = false;
    }
  }

  backtrack();
  return out;
}

// Swap version. No extra array, but the output is not sorted.
function permutationsBySwap(str) {
  const chars = [...str];
  const out = [];

  function backtrack(k) {
    if (k === chars.length) {
      out.push(chars.join(""));
      return;
    }
    const seen = new Set();
    for (let i = k; i < chars.length; i++) {
      if (seen.has(chars[i])) continue;   // duplicate test, per level
      seen.add(chars[i]);

      [chars[k], chars[i]] = [chars[i], chars[k]];   // choose
      backtrack(k + 1);                              // explore
      [chars[k], chars[i]] = [chars[i], chars[k]];   // un-choose
    }
  }

  backtrack(0);
  return out;
}

What it costs

There are n! permutations and each one takes O(n) to write out, so no algorithm can beat O(n · n!) if it has to produce all of them. Both versions here hit that bound. The output is the bottleneck, not the search.

This is worth internalising before optimising anything: 10 characters is 3.6 million permutations, 13 is over six billion. If a problem asks for all permutations of anything longer than about ten items, the problem is usually not really asking for that.

Check yourself