Palindrome Partitioning

Palindrome Partitioning is a classic backtracking problem. It teaches the core backtracking move — try a choice, recurse, then undo it — plus the idea of pruning: only explore a branch that can possibly lead to a valid answer.

The slow way first

You could generate every way to cut the string (there are 2^(n−1) of them), then throw out any partition that contains a non-palindrome. That works, but it wastes huge effort: you build a whole partition like ["aa", "b"] only to reject it at the very end, and you keep cutting deeper even after an early piece is already broken.

The question to ask: can I reject a bad branch the moment it goes wrong, instead of at the end? Yes — check each piece as you cut it, and refuse to recurse past a piece that is not a palindrome.

The idea: cut, check, recurse, undo

Walk a cut position start through the string. From start, try every possible next piece s[start:end]. Only if that piece is a palindrome do we add it to the current path and recurse from end. When start reaches the end of the string, the current path is one complete answer. After each recursive call we pop the piece back off — that is the backtracking step that lets us try the next cut.

The palindrome check is the pruning step: a non-palindrome prefix is dropped immediately, so we never waste time exploring partitions that are already doomed.

Walk through it

Step through the animation. The cells show the prefix currently under test; the tree shows the cut decisions. From start = 0 we first take 'a', then 'a', then 'b' — reaching the end with ['a','a','b']. We backtrack to start = 0, take the longer prefix 'aa', then 'b', giving ['aa','b']. Two leaves, two answers.

Pseudocode

result = []
backtrack(start = 0, path = []):
    if start == length of s:
        add a copy of path to result      # reached the end -> one answer
        return
    for end from start+1 to length of s:
        prefix = s[start:end]
        if prefix is a palindrome:         # the pruning check
            path.append(prefix)
            backtrack(end, path)           # recurse on the rest
            path.pop()                     # undo -> try next cut
return result

The Python solution

def partition(s):
    result = []
    def backtrack(start, path):
        if start == len(s):
            result.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):
            prefix = s[start:end]
            if prefix == prefix[::-1]:
                path.append(prefix)
                backtrack(end, path)
                path.pop()
    backtrack(0, [])
    return result

• result collects every valid partition; path is the partition we are currently building.
• The base case start == len(s) means we have consumed the whole string — path[:] stores a copy (the live path keeps changing as we backtrack).
• The for end loop tries every prefix length from start.
• prefix == prefix[::-1] is the palindrome test ([::-1] reverses the string). This is the prune: a non-palindrome prefix is skipped, so we never recurse past it.
• path.append → backtrack → path.pop is the backtracking trio: choose, explore, undo.

Complexity

In the worst case (a string like "aaaa", all palindromes) there really are 2^(n−1) partitions, so the output alone is exponential — no algorithm can beat that. The win from pruning is practical: on a typical string we abandon non-palindromic branches immediately instead of exploring them. The O(n) extra space is the recursion depth plus the current path.

When this pattern shows up

Practice