Palindrome Partitioning: Backtracking All Valid Splits

Given a string s, partition it such that every substring of the partition is a palindrome. Return all possible palindrome partitionings.

This is LeetCode 131: Palindrome Partitioning. At each position in the string, you choose where to make the next cut. The constraint is that the piece you cut off must be a palindrome. If it is, you recurse on the rest of the string. If it is not, you skip that cut entirely. The result is every way to split the string into palindromic pieces.

Examples:

• "aab" returns [["a","a","b"], ["aa","b"]]
• "a" returns [["a"]]

Why this problem matters

Palindrome Partitioning combines two skills: substring partitioning via backtracking and palindrome checking. You have seen both of these individually in problems like Subsets (backtracking over choices) and Palindromic Substrings (checking palindromes). This problem forces you to put them together.

The backtracking structure is the same choose-explore-unchoose skeleton you already know. The difference from Subsets is that the "choice" at each step is which prefix to cut off, and the "constraint" is that the prefix must be a palindrome. Non-palindromic prefixes are skipped, which prunes entire subtrees from the recursion.

The approach

The algorithm uses backtracking with palindrome checking as a gate:

1. Start at index 0 with an empty path.
2. At position start, try every substring s[start:end+1] for end from start to len(s) - 1.
3. If s[start:end+1] is a palindrome, add it to the current path and recurse from end + 1.
4. When start reaches the end of the string, the entire string has been partitioned into palindromes. Record the current path.
5. After recursing, pop the last element (unchoose) and try the next longer prefix.

The key insight is that non-palindromic prefixes are never added to the path. If s[start:end+1] is not a palindrome, you do not recurse. This avoids exploring branches that can never produce valid results.

The solution

def partition(s: str) -> list[list[str]]:
    result = []
    n = len(s)

    def is_palindrome(sub: str) -> bool:
        return sub == sub[::-1]

    def backtrack(start: int, path: list[str]):
        if start == n:
            result.append(path[:])
            return

        for end in range(start, n):
            substring = s[start:end + 1]
            if is_palindrome(substring):
                path.append(substring)
                backtrack(end + 1, path)
                path.pop()

    backtrack(0, [])
    return result

The outer function initializes result and calls backtrack(0, []). Inside backtrack, the base case fires when start == n, meaning the entire string has been consumed by palindromic pieces. At that point, the current path is a valid partition.

The for loop tries every possible end position for the current substring. For each end, it slices s[start:end+1] and checks if it is a palindrome. If so, it appends the substring to path, recurses from end + 1, and then pops the substring to backtrack.

The is_palindrome check is the pruning condition. Without it, you would generate all possible partitions (including ones with non-palindromic pieces) and then filter. With it, you never explore invalid branches at all.

Visual walkthrough

Let's trace through the algorithm on s = "aab". Watch how non-palindromic prefixes are pruned and valid partitions are collected at the leaves.

The recursion tree has three branches at the root: prefixes "a", "aa", and "aab". The prefix "aab" is not a palindrome, so that entire branch is pruned. Under "a", the remaining string "ab" produces two sub-branches: "a" (palindrome, leads to ["a","a","b"]) and "ab" (not a palindrome, pruned). Under "aa", only "b" remains, which is trivially a palindrome, producing ["aa","b"].

Optimized solution with DP preprocessing

You can precompute all palindrome substrings in O(n^2) to avoid redundant palindrome checks during backtracking:

def partition(s: str) -> list[list[str]]:
    n = len(s)
    dp = [[False] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 3 or dp[i + 1][j - 1]):
                dp[i][j] = True

    result = []

    def backtrack(start: int, path: list[str]):
        if start == n:
            result.append(path[:])
            return

        for end in range(start, n):
            if dp[start][end]:
                path.append(s[start:end + 1])
                backtrack(end + 1, path)
                path.pop()

    backtrack(0, [])
    return result

The dp[i][j] table is filled bottom-up. A substring s[i:j+1] is a palindrome if s[i] == s[j] and either the substring has fewer than 3 characters (length 1 or 2) or the inner substring s[i+1:j] is already known to be a palindrome. This gives O(1) palindrome lookups during the backtracking phase.

Complexity analysis

Time is O(n * 2^n) in the worst case. A string of n identical characters like "aaa...a" has 2^(n-1) valid partitions (every possible way to place dividers between characters). Each partition is up to length n, and copying it into the result costs O(n). The palindrome checks add at most O(n^2) preprocessing with DP or O(n) per check without it, but the dominant cost is the 2^(n-1) partitions.

Space is O(n) for the recursion stack and current path (ignoring the output). With DP preprocessing, the palindrome table takes O(n^2). The output itself can hold up to 2^(n-1) partitions.

Building blocks

Palindrome Partitioning is built from two reusable pieces.

Substring partitioning backtracking

The recursive structure of trying every prefix at each position, then recursing on the remainder, is the same pattern used in Subsets and word break style problems. The skeleton is:

def backtrack(start, path):
    if start == n:
        record(path)
        return
    for end in range(start, n):
        piece = s[start:end + 1]
        if valid(piece):
            path.append(piece)
            backtrack(end + 1, path)
            path.pop()

The only thing that changes between partitioning problems is the valid check. In Palindrome Partitioning, valid checks for palindromes. In word break, valid checks dictionary membership. In restore IP addresses, valid checks for valid octets. The skeleton is always the same.

Palindrome checking

The is_palindrome function is the same two-pointer convergence pattern from Palindromic Substrings and Valid Palindrome. Compare the first and last characters, move inward, repeat. In this problem, the quick sub == sub[::-1] one-liner works fine, but the underlying concept is the same opposite-end comparison you have drilled in other palindrome problems.

For the DP optimization, the palindrome table dp[i][j] is the same table used in Longest Palindromic Substring and Palindromic Substrings. If you have built that table before, the preprocessing step here is identical.

Edge cases

Before submitting, check these:

• Single character: "a" returns [["a"]]. A single character is always a palindrome.
• All same characters: "aaa" returns [["a","a","a"], ["a","aa"], ["aa","a"], ["aaa"]]. Every prefix at every position is a palindrome, so no pruning occurs and the answer has 2^(n-1) partitions.
• No palindromic partitions beyond single characters: "abc" returns [["a","b","c"]]. No multi-character substring is a palindrome, so the only valid partition splits every character individually.

From understanding to recall

You understand the recursion tree. You see how each prefix is checked for palindromes and how non-palindromic prefixes prune entire branches. But can you write the backtracking function, the palindrome check, and the base case from scratch in under two minutes?

That is what interviews demand. The palindrome partitioning problem combines two patterns: substring partitioning backtracking and palindrome checking. If you have drilled both building blocks independently, the combination is natural. If you have not, the details slip: forgetting to copy the path, getting the loop bounds wrong, missing the end + 1 in the recursive call.

The substring partitioning backtracking template is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Palindromic Substrings - The expand-around-center pattern for counting palindromes. Same palindrome checking concept used as the pruning gate here.
• Subsets - The foundational backtracking decision tree. Compare the include/skip pattern in Subsets to the prefix partitioning pattern here.