Palindrome Partitioning — Solution

Problem

Given a string, split it into substrings so that every piece is a palindrome, and return every possible way to do this. A single character always counts as a palindrome, so splitting into individual letters is always one valid answer.

• Input: s = "aab"
• Output: [["a","a","b"], ["aa","b"]]
• Explanation: "aa" is a palindrome and "b" is a palindrome, giving the second partition; splitting all three characters individually also works.

For s = "abc" the only valid partition is [["a","b","c"]], because "ab", "bc", and "abc" are all not palindromes — none of the multi-character prefixes or suffixes qualify.

Intuition

At every position you decide where to make the next cut — and you only cut when the piece you're taking is a palindrome. This is a backtracking search: commit to a palindrome prefix, recurse on what's left, then undo and try a longer prefix. The expensive hidden cost is checking whether each candidate prefix is a palindrome; building a lookup table in O(n²) before the search starts brings every such check down from O(n) to O(1).

Solution — Backtracking

Precompute which substrings are palindromes, then explore all valid cuts with standard backtracking: add a palindrome piece to the current path, recurse on the rest, then pop and try the next possible cut.

1. Build a 2D boolean table where is_pal[left][right] is True when s[left..right] is a palindrome, using the recurrence: outer characters must match, and the interior must also be a palindrome (substrings of length ≤ 2 need only the character match).
2. Fill the table with right as the outer loop so shorter substrings are ready before longer ones that depend on them.
3. Define backtrack(start, path) to explore all valid partitions beginning at index start.
4. Base case: when start == len(s), every character has been assigned to a palindrome piece — append a copy of path to the results.
5. For each end from start to len(s) - 1, if is_pal[start][end] is true, add s[start:end+1] to path, recurse with end + 1, then pop to undo the choice.

1def partition(s: str) -> list[list[str]]:
2    n = len(s)
3    is_pal = [[False] * n for _ in range(n)]
4
5    # outer loop is right so shorter substrings are filled before longer ones
6    for right in range(n):
7        for left in range(right + 1):
8            if s[left] == s[right] and (right - left <= 2 or is_pal[left + 1][right - 1]):
9                is_pal[left][right] = True
10
11    results = []
12
13    def backtrack(start: int, path: list[str]) -> None:
14        if start == n:
15            results.append(path[:])  # copy the list, not a reference to it
16            return
17        for end in range(start, n):
18            if is_pal[start][end]:
19                path.append(s[start:end + 1])
20                backtrack(end + 1, path)
21                path.pop()  # undo before trying a longer prefix
22
23    backtrack(0, [])
24    return results

Time: O(n · 2^n) — there are at most 2^(n−1) ways to partition the string and each takes O(n) to copy into the result; the O(n²) table build is dominated by this.
Space: O(n²) for the palindrome lookup table, plus O(n) recursion depth.

Complexity Summary

Common Mistakes

• Appending the path directly instead of a copy — results.append(path) stores a reference to the same list, which will be empty by the time backtracking finishes. Always append path[:] in Python or new ArrayList<>(path) in Java.
• Using the wrong loop order to build the palindrome table — iterating for left in range(n): for right in range(left, n) means when you try to look up is_pal[left+1][right-1] for a length-3+ substring, that cell hasn't been computed yet. Outer right, inner left ensures shorter substrings (smaller second index) are always ready.
• Omitting the pop after recursing — without path.pop(), the path accumulates every piece ever appended and all subsequent results are corrupted. Every backtracking problem has a mandatory undo step after each recursive call.
• Checking palindromes with a separate function inside the loop — a naive O(n) palindrome check inside the backtracking loop adds an extra factor of n to every recursive level, turning O(n · 2^n) into O(n² · 2^n). The precomputed table eliminates this.
• Using >= instead of == for the base case — start is always incremented to exactly end + 1, so it can only equal n, never exceed it. Using >= n is harmless but hides the invariant; using == n makes the contract explicit.

Related Problems

• palindromic-substrings — count how many substrings are palindromes; uses the exact same DP table
• word-break — partition a string using dictionary words instead of palindromes; same backtracking skeleton with a different validity check
• longest-palindromic-subsequence — DP over palindromic substructures; shares the substring interval DP intuition
• partition-equal-subset-sum — partition an array into two equal halves; different domain, same "try all valid splits and backtrack" structure
• subsets-ii — exhaustive enumeration with backtracking and deduplication; a clean companion problem for practicing the undo pattern