Palindrome Partitioning

Problem

Given a string s, partition it into contiguous substrings such that every substring is a palindrome. Return all possible such partitions.

A partition is an ordered list of non-empty pieces whose concatenation is exactly s. Each piece must read the same forwards and backwards (a single character is trivially a palindrome). Two partitions are different if they cut the string at different positions.

The order of the partitions in your answer does not matter, but within each partition the pieces must appear left to right as they occur in s.

Examples

• Input: s = "aab" → Output: [["a", "a", "b"], ["aa", "b"]] "a" | "a" | "b" splits every character (all trivially palindromes). "aa" | "b" merges the first two since "aa" is a palindrome. "aab" as one piece is not a palindrome, so it is excluded.
• Input: s = "a" → Output: [["a"]] A single character has exactly one partition.
• Input: s = "aba" → Output: [["a", "b", "a"], ["aba"]] Split into singletons, or keep the whole string since "aba" is itself a palindrome. "ab" | "a" is invalid because "ab" is not a palindrome.

Constraints

• 1 <= s.length <= 16.
• s consists of lowercase English letters only.

The small bound (<= 16) indicates that an exponential enumeration of cut points is expected: there can be up to 2^(n-1) partitions.

Think about it first

TL;DR

Backtrack over palindromic prefixes; optionally precompute a DP palindrome table to make each check O(1) — O(n · 2^n) time, O(n) recursion space (plus O(n^2) for the table).

Approach 1 — Backtracking with an on-the-fly palindrome check

Try every possible first cut. For each end, the prefix s[start:end] is a candidate piece; if it is a palindrome, commit to it and recursively partition the remaining suffix s[end:]. When start reaches the end of the string, the current path is a complete valid partition.

The recursion tree for s = "aab" shows each choice of palindromic prefix. Dead ends (non-palindrome prefixes) are pruned immediately.

flowchart TD
    A["backtrack(0)"] -->|"a"| B["backtrack(1)"]
    A -->|"aa"| C["backtrack(2)"]
    A -.->|"aab" not palindrome| X1["pruned"]
    B -->|"a"| D["backtrack(2)"]
    B -.->|"ab" not palindrome| X2["pruned"]
    D -->|"b"| E["backtrack(3): record [a, a, b]"]
    C -->|"b"| F["backtrack(3): record [aa, b]"]

from typing import List

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

    def is_palindrome(left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

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

    backtrack(0)
    return result

Complexity: O(n · 2^n) time — there are up to 2^(n-1) partitions and constructing/validating each costs O(n) — and O(n) auxiliary space for the recursion stack and path (excluding the output). With n <= 16 this is comfortably fast.

Approach 2 — Precompute a DP palindrome table

Across the recursion the same substring gets palindrome-tested repeatedly. Precompute once: is_pal[i][j] is True when s[i..j] is a palindrome. The recurrence is that s[i..j] is a palindrome exactly when s[i] == s[j] and the inside s[i+1..j-1] is a palindrome (or the inside is empty, i.e. j - i < 2). Fill it so that shorter substrings are known before longer ones — iterating i from high to low guarantees is_pal[i+1][j-1] is already computed.

from typing import List

def partition(s: str) -> List[List[str]]:
    n = len(s)
    is_pal = [[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 < 2 or is_pal[i + 1][j - 1]):
                is_pal[i][j] = True

    result: List[List[str]] = []
    path: List[str] = []

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

    backtrack(0)
    return result

Walkthrough on s = "aab" (n = 3):

• Build is_pal: is_pal[0][0]=is_pal[1][1]=is_pal[2][2]=True (singletons). is_pal[0][1]: s[0]=s[1]='a' and length 2 → True ("aa"). is_pal[1][2]: s[1]='a' != s[2]='b' → False ("ab"). is_pal[0][2]: s[0]='a'==s[2]='b'? no → False ("aab").
• backtrack(0), end=0: is_pal[0][0] true → piece "a", path ["a"], recurse.
  • backtrack(1), end=1: is_pal[1][1] true → "a", path ["a","a"], recurse.
    • backtrack(2), end=2: is_pal[2][2] true → "b", path ["a","a","b"]; backtrack(3) records ["a","a","b"]. Pop.
  • backtrack(1), end=2: is_pal[1][2] false → skip. Pop "a".
• backtrack(0), end=1: is_pal[0][1] true → "aa", path ["aa"], recurse.
  • backtrack(2), end=2: "b" → path ["aa","b"]; backtrack(3) records ["aa","b"]. Pop.
• backtrack(0), end=2: is_pal[0][2] false → skip.

Result: [["a","a","b"], ["aa","b"]], matching the example.

Complexity: O(n^2) to build the table, then O(n · 2^n) for the enumeration — asymptotically the same as Approach 1 but with each palindrome check reduced to a single O(1) lookup. Space is O(n^2) for the table plus O(n) recursion.

Common pitfalls

• Off-by-one on the slice bounds. Decide whether end is inclusive or exclusive and keep the palindrome check and the slice consistent (the two approaches above deliberately use different conventions — mixing them silently drops or duplicates a character).
• Appending a reference instead of a copy. result.append(path) stores the same list object that keeps mutating; use path[:] to snapshot it.
• Forgetting to pop after recursing. Without undoing the choice, path leaks pieces into sibling branches.
• Skipping single characters as pieces. Every single character is a palindrome, so the loop must allow length-1 pieces; the all-singletons partition is always valid.

Pattern takeaway

Partition-style backtracking asks “where do I cut first?” — enumerate every valid prefix, recurse on the remaining suffix, and undo. When the validity test on substrings is expensive and repeated, precompute it with an interval DP table so the search itself stays a clean O(1)-per-check tree walk.