Palindrome Partitioning

Generate all possible ways to split a string into palindrome substrings.

backtracking recursion palindrome partition

A palindrome is a string that reads the same forward and backward. Given a string `s`, partition `s` such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of `s`. A palindrome partitioning is a set of substrings that concatenated in order form exactly `s`. The order of substrings within each partition must follow the order of characters in `s`. The order of partitions in the returned list does not matter. You must implement the function with the exact signature:

```python
def partition(s: str) -> list[list[str]]:
```

For example, for `s = "aab"` the possible palindrome partitions are:

- `["a", "a", "b"]`
- `["aa", "b"]`

Return a list of lists, where each inner list contains strings. If `s` is empty, return `[[]]` (one partition containing zero substrings) because the empty string can be considered a valid partition.

Constraints

`0 <= len(s) <= 15`
`s` consists of lowercase English letters only.
The result can be large but within memory limits for the given constraint.
Time complexity: You must enumerate every valid partition. A backtracking approach with memoization is acceptable. Avoid exponential time beyond the number of partitions.

Example

```python
>>> partition("aab")
[['a', 'a', 'b'], ['aa', 'b']]
>>> partition("a")
[['a']]
>>> partition("")
[[]]
>>> partition("abba")
[['a', 'b', 'b', 'a'], ['a', 'bb', 'a'], ['abba']]
```

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use backtracking: at each step, try every possible prefix that is a palindrome and recurse on the remaining suffix.

A helper function `is_palindrome` can check substring equality with its reverse.

Think about pruning: if a prefix is not a palindrome, skip it entirely.

The empty string case: returning `[[]]` is the base case for recursion when `s` is empty.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.