Palindrome Partitioning
Palindrome Partitioning: split string s into pieces so every piece is a palindrome; return all such partitions.
- 1 <= s.length <= 16
- s contains only lowercase English letters.
Intuition
Palindrome partitioning asks for every way to cut a string so that each piece is a palindrome. It is an enumeration, not a search for one answer, so the output can be large and the work is inherently exponential.
The framing that makes it tractable is to think about only the first cut. Pick where the first piece ends. If that piece is a palindrome, it is a legal opening move, and what remains is the same problem on a shorter string. That self-similarity is the recursion.
So at position start, try every end position. For each one where s[start:end+1] is a palindrome, record the piece and recurse from end + 1. When start reaches the end of the string, every character has been consumed by some palindromic piece, and the accumulated path is one complete valid partition.
Two things keep this from exploding worse than it must:
- The palindrome check happens before recursing, so a non-palindromic prefix never generates a subtree at all.
- The path is undone after each branch — append the piece, recurse, then remove it — so sibling branches start from a clean state.
That second point is what backtracking means here. Forgetting the removal does not crash; it silently produces partitions containing pieces from unrelated branches.
Backtracking over cut points rather than elements: at each position, try every substring starting there, and recurse past whichever one you accepted. The palindrome test is the pruning — it stops whole branches before they're explored. Any "split the string into valid pieces" problem takes this shape.
Approach
Before reading on: price up what the direct approach costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(n · 2ⁿ) time and O(n) space.
Frame the problem as choosing the first cut
From index start, every end where s[start:end+1] is a palindrome is a legal first piece. What follows is the identical problem on the remaining suffix, which is what makes a single recursive function sufficient.
Test the piece before recursing
Check whether the candidate substring is a palindrome first, and only recurse when it is. Placing the check before the call prunes the entire subtree beneath an invalid prefix — the main reason this runs in practice despite the exponential bound.
Append, recurse, then remove
Push the piece onto the current path, recurse from end + 1, then pop it before trying the next end. The pop is mandatory — without it, pieces from one branch leak into the next and the output contains partitions that were never valid.
Record a complete partition at the end
When start equals the string length, every character belongs to some palindromic piece. Append a copy of the current path to the results — appending the list itself stores a reference that later mutations will corrupt.
Precompute the palindrome table if asked to optimise
The same substring is tested repeatedly across branches. A dp[i][j] table marking palindromic substrings, filled in O(n²) up front, makes each check O(1). Worth mentioning as the follow-up, though it does not change the exponential output bound.
Cost of the enumeration
A string of n characters has up to 2^(n−1) cut positions, and each valid partition costs O(n) to copy, giving O(n · 2ⁿ) time in the worst case — a string like "aaaa" where every substring is a palindrome. Space is O(n) for the recursion and path, plus the output.
Solution & live demo
Common pitfalls
Recursing from start + 1 instead of end + 1
backtrack(start + 1)
backtrack(end + 1)
The piece just accepted spans start..end, so the next piece begins after end. Advancing by one re-consumes characters already placed and produces overlapping partitions.
Testing the whole string for palindromes up front
if s != s[::-1]: return []
if is_pal(start, end):
path.append(s[start:end+1])The pieces must be palindromes, not the input. "aab" isn't a palindrome yet partitions fine into ["a", "a", "b"].
Storing the path by reference
res.append(path)
res.append(path[:])
path is mutated as the search unwinds, so every stored reference ends up empty. The snapshot must be a copy taken at the moment the partition is complete.
Edge cases
Every 1-char string is a palindrome → [[c]].
Every cut works — output size grows exponentially; that's inherent to the problem.