Given a string, return every way to partition it so that every piece is a palindrome.
Before you code
Each choice is where the next piece ends. Only pieces that are palindromes are worth choosing, which prunes most of the tree.
Hints
- Recurse with the start index of the remaining string.
- For each end index, if
s[start:end + 1]is a palindrome, choose it, recurse fromend + 1, then unchoose. - Precompute a table
is_pal[i][j]so each palindrome test is O(1) instead of O(length).
Production & complexity notes
When solving Palindrome partitioning on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Backtracking basics to reinforce the underlying pattern.
What it practices
The choose, explore, unchoose pattern and pruning, from Backtracking basics.