Palindrome Partitioning

Signal

"Every way to split a string so each piece satisfies a property" backtracks over cut points: choose how long the next piece is, check the property, and only recurse into the remainder if it holds.

Approach

Backtrack from a start index. At each step, try every possible end point for the next piece; if s[start:end] is a palindrome, add it to the path and recurse on the remainder starting at end. Once start reaches the end of the string, the current path is one complete valid partition.

Skeleton

def backtrack(start, path):
    if start == len(s): results.append(copy of path); return
    for end in range(start + 1, len(s) + 1):
        piece = s[start:end]
        if is_palindrome(piece):
            path.append(piece)
            backtrack(end, path)
            path.pop()

Solution

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

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

    def backtrack(start: int) -> None:
        if start == n:
            results.append(path[:])
            return
        for end in range(start + 1, n + 1):
            piece = s[start:end]
            if is_palindrome(piece):
                path.append(piece)
                backtrack(end)
                path.pop()

    backtrack(0)
    return results

Complexity

O(n · 2^n) time in the worst case — up to 2^(n-1) ways to place cuts, each costing up to O(n) to check and copy. Precomputing an O(n²) is_palindrome table (built from smaller substrings outward) turns each check into O(1), which matters far more when the string has few valid cuts and many failed attempts.

Pitfalls

• Re-slicing and reversing piece from scratch on every call — fine for short strings, but a precomputed DP table of palindrome ranges avoids redundant work across overlapping substrings.
• Off-by-one on the slice range — end must run through n inclusive (since s[start:end] is exclusive of end), not stop at n - 1.
• This returns every partition — a follow-up asking for just the minimum number of cuts is a different (and more DP-shaped) problem; don't over-adapt this backtracking solution to answer it directly.