Palindrome Partitioning
Split string s into pieces so every piece is a palindrome; return all such partitions.
Intuition
Choose the first piece, then the rest of the string is the same problem again. At each position try every palindromic prefix, recurse on the remainder, and backtrack. The palindrome check prunes whole subtrees the moment a prefix isn't one.
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
Frame as choices at a cut point
From index start, every end where s[start:end+1] is a palindrome is a legal next piece.
Recurse and backtrack
Append the piece, recurse from end+1; when start reaches the end of the string the path is one complete answer. Pop and try the next cut.
Prune early
Non-palindromic prefixes are never extended — the check happens before recursion, keeping the tree small.
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.