Example 1
Input
palindrome_partitions('aab')
Output
[['a', 'a', 'b'], ['aa', 'b']]
Two ways: split into single letters 'a','a','b' or take 'aa' then 'b'.
Full lesson preview
Find all palindrome partitions of a string with pruning
Compute every way to partition a string so that every substring is a palindrome, using DP pruning to speed recursion.
Python practice28 minRecursion & BacktrackingAdvancedLast updated March 27, 2026
Problem statement
Given a string s, return all possible palindrome partitioning of s. A palindrome partitioning is a decomposition of the input string into substrings such that every substring is a palindrome. Use recursion (backtracking) and prune using a precomputed table that allows constant-time palindrome checks to avoid redundant work. Return the list of partitions in the order discovered by exploring prefixes from left to right.
Task
Use recursion with pruning (precomputed palindrome table) to generate all palindrome partitions of a string efficiently.
Examples
Input format
A single string s (letters may include lowercase/uppercase characters).
Output format
A list of lists of strings where each inner list is a palindrome partition. Example: [['a','a','b'], ['aa','b']]
Constraints
0 <= len(s) <= 15. Solutions should avoid repeated palindrome checks by precomputing a palindrome table (O(n^2) time/space) and then backtracking.
Samples
Sample 1
Input
palindrome_partitions('efe')
Output
[['e', 'f', 'e'], ['efe']]
Either single letters or the whole string 'efe' which is a palindrome.