Palindrome Partitioning

Given a string, list every way to cut it into pieces where each piece is a palindrome. For "aab" the answers are "a | a | b" and "aa | b".

This one is worth doing after n-queens because the constraint has a different character. A queen placement is rejected by comparing against other placements. A cut is rejected by looking at the piece itself, which means the test is independent of everything else on the path, and that opens an optimisation the earlier problems did not have.

What the choices are

At each step you are standing at some position in the string and deciding where the next piece ends. If the piece from here to there is a palindrome, cut it and carry on from the next character. If not, that cut is impossible, so try a longer piece.

A string of length n has n-1 gaps, so there are 2^(n-1) possible cut patterns. The palindrome test rejects most of them long before they are fully built, which is why the tree stays small.

There is always at least one answer, because single characters are palindromes. The all-singletons partition is the floor.

Step through it

The strip shows the string. Green pieces are cut and locked in for the current branch. The copper block is the piece being tested right now, and it turns coral when the test fails.

Watch the first branch: it tries "a", which passes, then from position 2 tries "a" again, then "b", and so on down to the all-singletons answer. Then it backs all the way up and tries "aa" as the first piece instead.

The rejections are the interesting frames. "aab" fails, so the entire family of partitions starting with "aab" is never built. On this five-character string that is a handful of branches; on a twenty-character string it is most of the search.

Try "banana" too. It has far fewer partitions than "aabaa" despite being longer, because it has fewer palindromic substrings to cut on.

The repeated-work problem

Turn on the palindrome table in the widget. Every cell is one substring, marked T if it reads the same both ways.

Now notice how often the naive version recomputes those. The piece "aa" at position 1 gets tested on the branch that starts with "a", and again on a branch that reached position 1 by a different route. Each test walks the substring, so it is O(k) for a piece of length k, done over and over for the same k.

Precomputing the whole table costs O(n^2) time and O(n^2) space, and turns every later test into a single lookup. The recurrence is short: isPal[i][j] is true when s[i] === s[j] and the inside isPal[i+1][j-1] is also true, with pieces of length 1 and 2 as the base cases.

This does not change the worst case, because the output can still be exponential in size and you have to write all of it. It removes a factor of n from the work spent deciding, which in practice is the part that hurts.

In code

function partition(s) {
  const n = s.length;

  // isPal[i][j]: does s[i..j] read the same both ways?
  // Built by increasing length so the inside is always known first.
  const isPal = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let i = 0; i < n; i++) isPal[i][i] = true;
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      isPal[i][j] = s[i] === s[j] && (len === 2 || isPal[i + 1][j - 1]);
    }
  }

  const out = [];
  const parts = [];

  function backtrack(start) {
    if (start === n) {
      out.push([...parts]);
      return;
    }

    for (let end = start; end < n; end++) {
      if (!isPal[start][end]) continue;      // prune: no cut here can work

      parts.push(s.slice(start, end + 1));   // choose
      backtrack(end + 1);                    // explore
      parts.pop();                           // un-choose
    }
  }

  backtrack(0);
  return out;
}

// partition("aab") -> [["a", "a", "b"], ["aa", "b"]]

The related question that is not backtracking

A common follow-up asks for the minimum number of cuts rather than every partition. That question should not be answered with this algorithm.

Enumerating all partitions and taking the smallest works but is exponential for no reason. The minimum-cuts version only needs one number per position, so it is a straight O(n^2) dynamic program: the best cut count ending at position j is one more than the best ending just before some palindromic piece that finishes at j.

This is the boundary described on the introduction page. Wanting every answer points at backtracking. Wanting the best answer, with subproblems that repeat, points at dynamic programming.

Check yourself