Pattern Recognition Drill
Medium Backtracking
The Problem
Partition a string so every substring is a palindrome. Return all partitions.
What approach would you use?
Think about it before scrolling down.
At each position, try all prefixes that are palindromes. Recurse on remaining suffix. Collect at end.
Precompute is_palindrome[i][j] table to speed up palindrome checks within the backtracking.
Common Trap
The palindrome check inside backtracking can be precomputed with DP to avoid redundant work.