Palindrome Partitioning

def partition(s):
    res, path = [], []
    def back(start):
        if start == len(s):
            res.append(path[:])  # a copy
            return
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]
            if piece == piece[::-1]:  # mirror
                path.append(piece)
                back(end)
                path.pop()
    back(0)
    return res

Palindrome Partitioning. Cut a string into pieces so every piece is a palindrome, the same forwards and backwards. Return every way to do it.

Take A, A, B. Cut after every letter: A, A, B. Single letters are always palindromes. Or keep A A, then B. Two partitions.

The naive way: each gap between letters is cut or not, so there are two to the n minus one patterns. Make them all, then check the pieces. Most fail, and only at the end. Twenty letters means over half a million patterns.

Backtracking checks as it cuts. From a start position, try every end, and hold the piece up to a mirror. Not a palindrome? Skip it, and every partition that begins with it. A palindrome? Cut it and recurse from the next letter. When start reaches the end, record the pieces. Then pop the last one and try the next end.

In code: if start equals the length, save a copy of the path. Otherwise, loop over every end. If that slice is a palindrome, push it, recurse, and pop it.

On A, A, B: A works, so recurse. A again, then B, and start hits the end: record A, A, B. Pop back. A B fails the mirror: pruned. A A works, then B: record A A, B. A A B fails. Done.

Worst case, like all A's, every cut works: two to the n minus one partitions, each copied in order n. So time is order n times two to the n. The recursion is at most n deep, so extra space is order n.

Try every end, cut only mirrors, and backtrack. That's Palindrome Partitioning.