Cutting a string into palindromes
Palindrome partitioning asks for every way to split a string so that each piece reads the same forwards and backwards. The cut points are the decisions; the constraint is that each resulting segment is a palindrome.
Backtracking over cut positions
Walk a start index along the string. From the current start, try every possible end position:
- Take the substring from start to that end as the next piece.
- If that substring is a palindrome, append it to the path and recurse from just past it.
- Otherwise skip this length and try a longer piece.
- When the start reaches the end of the string, the current path is one valid partition.
Each branch corresponds to choosing how long the next palindromic chunk is, so the search explores all valid groupings.
Speeding up the test
Checking each candidate substring fresh is wasteful. Precompute a table marking which start and end pairs form palindromes, built with dynamic programming, so each palindrome test inside the recursion becomes a single lookup.
Key idea
You backtrack over where to cut, accepting a piece only when it is a palindrome, and a precomputed palindrome table turns each costly check into a constant-time lookup.