131. Palindrome Partitioning

Problem¶

Return every way to split s into nonempty substrings where each substring is a palindrome.

"aab" -> [["a", "a", "b"], ["aa", "b"]]

Key trick¶

Precompute which substrings are palindromes, then backtrack over valid cut positions.

Trap¶

Common mistakes are forgetting to copy the current partition, forgetting to undo a choice, or repeatedly reversing substrings instead of using constant-time palindrome lookup.

Why is it interesting?¶

It combines dynamic programming with backtracking and demonstrates that runtime must be output-sensitive because exponentially many partitions may exist.

Python solution¶

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        n = len(s)
        is_palindrome = [[False] * n for _ in range(n)]

        # A substring is a palindrome when its ends match and its
        # interior is empty, one character, or already a palindrome.
        for start in range(n - 1, -1, -1):
            for end in range(start, n):
                is_palindrome[start][end] = (
                    s[start] == s[end]
                    and (
                        end - start <= 2
                        or is_palindrome[start + 1][end - 1]
                    )
                )

        res = []
        cur = []

        def backtrack(start) -> None:
            if start == n:
                # Copy because cur is mutated during backtracking.
                res.append(cur.copy())
                return

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

        backtrack(0)
        return res

Precomputation takes \(O(n^2)\) time and space. Enumeration takes \(O(n2^n)\) time in the worst case, proportional to the output size.

Comment on my solution¶

Your backtracking is correct and clean, including copying the partition and undoing each choice.

Building a reversed string for every candidate adds repeated allocations and makes each palindrome check \(O(k)\).
A precomputed palindrome table reduces each check to \(O(1)\) while preserving the same backtracking structure.

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        result = []
        partition = []

        def backtrack(start):
            if start == len(s):
                result.append(partition[:])
                return

            for end in range(start, len(s)):
                t = s[start:end + 1]
                if t == "".join(reversed(t)):
                    partition.append(t)
                    backtrack(end + 1)
                    partition.pop()
        backtrack(0)
        return result

Solution().partition("aab") # [['a', 'a', 'b'], ['aa', 'b']]
Solution().partition("a") # [['a']]
Solution().partition("aabcb") # [['a', 'a', 'b', 'c', 'b'], ['a', 'a', 'bcb'], ['aa', 'b', 'c', 'b'], ['aa', 'bcb']]