Example
Input
s = 'aab'
Output
[['a', 'a', 'b'], ['aa', 'b']]
Two valid palindrome partitions: split into single letters or 'aa' + 'b'.
Full lesson preview
Partition a string into palindromic substrings
Return all possible palindrome partitions of a string via recursion and backtracking.
Python practice14 minRecursion & BacktrackingIntermediateLast updated March 27, 2026
Problem statement
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings. Use recursion with backtracking to explore splits. If s is an empty string, return an empty list []. The order of partitions should reflect a left-to-right DFS (i.e., try shorter left segments first).
Task
Generate all ways to partition the input string such that every substring in the partition is a palindrome.
Examples
Input format
A single string s. You will call partition_palindromes(s).
Output format
A list of lists. Each inner list is a partition of substrings, e.g. [['a','a','b'],['aa','b']].
Constraints
0 <= len(s) <= 16. Use caching for palindrome checks for efficiency when needed.
Samples
Sample 1
Input
s = 'aaa'
Output
[['a', 'a', 'a'], ['a', 'aa'], ['aa', 'a'], ['aaa']]
All palindromic ways to partition 'aaa'.