Given a string, cut it into pieces so that every piece reads the same forwards and backwards — find every way to do that, not just one. Like every other Backtracking entry on this site, there's no formula for which cuts work: decide on one cut at a time, and the instant a candidate piece fails, abandon it. What's different here is what makes a candidate fail. N-Queens, Sudoku, Graph Coloring, Hamiltonian Path/Cycle, and Word Search all reject a candidate because it conflicts with something already placed. Subset Sum rejects with arithmetic instead, but still arithmetic about what's already been chosen — a running total. This page's candidate — the next piece to cut off — is rejected or accepted purely by looking at itself: is this exact substring a palindrome? Nothing about the pieces already cut elsewhere in the string changes that answer. It's the first entry on this site where the whole rejection rule could, in principle, be looked up in a precomputed table built before the search ever starts (see Pitfalls).
A fixed 5-character string, aabaa, not user-editable, same convention as this
site's other fixed-content interactive demos. The search tries the shortest possible next piece
first: starting from the leftmost uncut character, it grows a candidate one character at a time
and tests whether that candidate is a palindrome. A candidate that passes is committed
(shown in green) and the search recurses on whatever's left; a candidate that fails is
rejected (shown faded) and the next, longer candidate from the same starting point
is tried instead. Once every character is committed, that combination of pieces is a full solution —
recorded, then the search backs out to try other cuts.
A 5-character string has 24 = 16 possible ways to place cuts between
its characters (each of the 4 gaps is either cut or not) — checking every one by brute force and
keeping the ones where every resulting piece is a palindrome finds exactly 6
valid partitions. The backtracking search above finds the same 6, computed
directly from the demo's own reference implementation below:
a|a|b|a|a, a|a|b|aa, a|aba|a, aa|b|a|a,
aa|b|aa, and aabaa itself. It reaches all six after
22 palindrome checks across 15 recursive calls, split between
14 accepted candidates (each one immediately recursed into, and later backtracked
out of) and 8 rejected ones — far fewer than testing all 16 cut combinations from
scratch, since a single rejected candidate (like ab, the very first 2-character piece
tried) prunes every longer combination that would have started with it, without trying any of
them individually.
function palindromePartitions(s) {
const n = s.length;
const solutions = [];
const cur = [];
function isPalindrome(i, j) {
while (i < j) {
if (s[i] !== s[j]) return false;
i++; j--;
}
return true;
}
function explore(start) {
if (start === n) {
solutions.push(cur.slice());
return;
}
for (let end = start; end < n; end++) {
if (isPalindrome(start, end)) {
cur.push(s.slice(start, end + 1));
explore(end + 1);
cur.pop(); // backtrack: undo this cut and try a longer one
}
}
}
explore(0);
return solutions;
}Verified against a brute-force check of all 2n-1 cut-point combinations
on the page's own string (16 combinations, 6 valid) and, separately, against the same brute-force
oracle on every string up to length 8 built from a 3-letter alphabet — 3,280 strings, every one a
match.
Forgetting cur.pop() after the recursive call doesn't change how many
solutions are found — it silently corrupts every solution after the first. It's tempting
to think a missing backtrack step would show up as an obviously wrong count, the way it does
elsewhere on this site. Here it doesn't: checked directly against this page's own string with the
pop() removed, the search still reports exactly 6 solutions — the
same true number — but every one after the first is garbage. The pieces from every earlier,
already-abandoned branch stay in cur forever, so what gets recorded as the second
"solution" is a | a | b | a | a | aa — six pieces concatenating to
aabaaaa, seven letters, not this five-letter string at all — and the sixth is
fourteen pieces long, concatenating to twenty-three letters. The count looks right; the content is
wrong from the second result onward. A check that only counts solutions instead of reading their
content would ship this bug.
Checking each candidate's palindrome-ness from scratch, with no precomputed table, means
the same substring can get re-checked many times over — because explore(start)
only depends on start, not on which pieces led there, so the same starting index gets
re-entered, and every one of its candidates re-tested, once for every different partition of the
prefix in front of it. Not dramatic on this page's own short string — 22 total checks cover only
15 distinct (start, end) pairs, a 1.47x redundancy — but it grows with the input, not
with a fixed constant: checked with a throwaway script (not reproducible in this page's own
6-checks-per-position demo), a 12-character run of the same letter pushes the same measurement to
255 total checks over just 36 distinct pairs, a 7.08x redundancy. Precomputing a palindrome table
for every (i, j) pair once, up front, turns every check into an O(1) lookup and
removes the redundant recomputation entirely — without changing which partitions get found, since
the table only replaces how the same true/false answer gets produced.
Time: O(n · 2n) worst case — a string of n
identical characters is entirely made of palindromes at every possible cut, so all
2n-1 partitions are valid and every one gets built and copied, each costing
up to O(n). The redundant-recheck pitfall above changes the constant factor a
precomputed table would remove; it doesn't change this exponential order, since enumerating every
valid partition of an all-palindrome string is exponential in the output size alone, precomputed
table or not. Space: O(n) for the recursion stack and the in-flight
cur array — only one partial partition is ever held mid-search. The final
solutions array does grow with the total output size, which is itself exponential in
the worst case; that's the size of the answer, not overhead the algorithm adds on top of it.
A related but different question — not every way to partition into palindromes, just the
fewest cuts needed — drops the exponential entirely: it's solvable by a bottom-up table in
O(n2), the same trade this site's
0/1 Knapsack makes against
Subset Sum's own backtracking search. That table only
needs to know how many cuts a minimum requires, never every distinct way to place them —
this page's own search answers a strictly harder question, and pays for it in kind. See
Choosing a Backtracking Strategy for how
this page's self-contained rejection rule compares to the other nine entries' own rules.