Hard · Partition Backtracking
Understand → Visualise → Practice.
Return every way to split the string so that every part is a palindrome.
Every partition starts with some palindromic prefix. Try each one, then partition the remaining suffix the same way.
For each end index, take text[start:end] if it is a palindrome.
Add the part to the path and partition from end.
When start reaches the end of the string, save a copy of the path.
O(n × 2ⁿ) time in the worst case, O(n) recursion depth.
Checking palindromes by building new reversed strings repeatedly is slow; precompute a palindrome table for long inputs.
Read the full guide first: Recursion and Backtracking.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.