We need to find every way to split a string into parts where each part reads the same forwards and backwards. This is not about finding the fewest cuts or the longest palindrome. We need all valid partitionings.

Splitting a string means placing dividers between characters. For "aab", the dividers "a|a|b" and "aa|b" both produce all-palindromic pieces, so both are valid answers.

This is a sequence of decisions, one per position. Starting from the left, we pick a palindromic prefix, then recursively partition the remainder. When we reach the end of the string with every piece being a palindrome, we have a valid partitioning.

Key Constraints:

Intuition

Build partitions left to right. Starting from index 0, try every possible first piece: "a", "aa", "aab". If a piece is a palindrome, recurse on the rest of the string. On reaching the end, every piece collected along the way is palindromic, so the path is a valid partition.

This is backtracking. At each position we explore multiple choices (where to end the current piece) and undo a choice before trying the next one.

To check whether a piece is a palindrome, compare characters from both ends and move inward. This takes O(n) time per check, which is fine when n is at most 16.

Algorithm

Example Walkthrough

Code

The repeated work here is in the palindrome checks. Every time we consider substring s[i..j], we re-scan it character by character, even if we already checked the same substring in a different branch. Precomputing all palindrome information once turns each check into an O(1) lookup.

Intuition

The backtracking from Approach 1 already explores exactly the partitions we need, so the search itself stays. What changes is the palindrome check: a 2D table lets us answer "is s[i..j] a palindrome?" in O(1).

The recurrence behind the table: a substring s[i..j] is a palindrome if and only if s[i] == s[j] and the inner substring s[i+1..j-1] is also a palindrome. When the inner part has length 0 or 1, it is a palindrome by definition, so any substring of length 1 or 2 with matching endpoints qualifies directly.

We fill the boolean table isPalin[i][j] in order of increasing substring length. By the time we evaluate a substring of length L, every substring of length L-2 has already been filled, so the inner lookup isPalin[i+1][j-1] is ready. After the table is built, the backtracking tree is identical to Approach 1, but each node does an O(1) lookup instead of an O(n) scan.

Algorithm

Example Walkthrough

Code

The palindrome table makes each check O(1), but different backtracking branches still re-explore the same suffix. Whenever the search reaches index i, it recomputes the partitions of s[i..n-1] from scratch, even though that set never depends on how we arrived at i. The next approach computes each suffix once and stores it.

Intuition

The set of valid partitions of a suffix s[i..n-1] depends only on i, not on the choices made before index i. Approach 2 recomputes this set in every branch that reaches i. We can compute it once instead.

Define dp[i] as the list of all valid palindrome partitions of the suffix starting at index i. To build dp[i], try every index j from i to n-1 where s[i..j] is a palindrome. For each such j, prepend the piece s[i..j] to every partition already stored in dp[j+1]. The base case is dp[n] = [[]], the single empty partition of the empty suffix.

Because dp[i] only ever reads dp[j+1] for j >= i, filling the array from right to left guarantees every dependency is ready before it is needed. The result for the whole string is dp[0].

Algorithm

Example Walkthrough

Code