Module 16 · Backtracking and Combinatorial Search

159. Palindrome Partitioning

Interview · Download this solution · All solutions and shared helpers

Problem

Partition text into nonempty palindromic substrings and return every partition. Preserve substring order and try each next cut from shortest to longest. Empty text returns [[]]. Characters are compared exactly, without case folding or normalization.

Examples

Example 1

palindrome_partitions("aab")
=> [['a', 'a', 'b'], ['aa', 'b']]

The first two letters may be separate or one palindrome.

Example 2

palindrome_partitions("")
=> [[]]

The empty prefix already covers the whole input.

Example 3

palindrome_partitions("aba")
=> [['a', 'b', 'a'], ['aba']]

Both singleton cuts and the whole palindrome are valid.

Reveal the worked solution and reasoning

Why this mechanism works

At index start, the next piece can end at any later position, but only a palindrome is a legal choice. Precompute which intervals are palindromes so the recursive search can focus on partitions. An interval is palindromic when its endpoints match and its interior is palindromic, with lengths one and two as bases.

State and boundaries

pal[i][j] describes inclusive substring text[i:j+1]. path partitions text[:start] completely into palindromes.

Protocol

Fill palindrome intervals from larger start indices toward smaller ones.
At start==n copy path.
Try each palindromic interval starting at start.
Append its substring, recurse after its end, then undo.

Visualization

aab
cut a | a | b -> all palindromes
cut aa | b    -> all palindromes
cut a | ab    -> reject ab

Python implementation

def palindrome_partitions(text):
    n = len(text)
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = text[i] == text[j] and (j - i < 2 or pal[i + 1][j - 1])
    output, path = [], []
    def visit(start):
        if start == n:
            output.append(path.copy())
            return
        for end in range(start, n):
            if pal[start][end]:
                path.append(text[start:end + 1])
                visit(end + 1)
                path.pop()
    visit(0)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

palindrome_partitions("aab")

L2 palindrome_partitions: n = len(text)
text='aab'; n=3

L3 palindrome_partitions: pal = [[False] * n for _ in range(n)]
text='aab'; n=3; _=0

L3 palindrome_partitions: pal = [[False] * n for _ in range(n)]
text='aab'; n=3; _=1

L3 palindrome_partitions: pal = [[False] * n for _ in range(n)]
text='aab'; n=3; _=2

L3 palindrome_partitions: pal = [[False] * n for _ in range(n)]
text='aab'; n=3; pal=[[False, False, False], [False, False, False], [False, False, False]]

L4 palindrome_partitions: for i in range(n - 1, -1, -1):
text='aab'; n=3; pal=[[False, False, False], [False, False, False], [False, False, False]]; i=2

L5 palindrome_partitions: for j in range(i, n):
text='aab'; n=3; pal=[[False, False, False], [False, False, False], [False, False, False]]; i=2; j=2

L6 palindrome_partitions: pal[i][j] = text[i] == text[j] and (j - i < 2 or pal[i + 1][j - 1])
text='aab'; n=3; pal=[[False, False, False], [False, False, False], [False, False, True]]; i=2; j=2

... 38 intermediate state changes omitted ...

L15 visit: visit(end + 1)
start=0; n=3; output=[['a', 'a', 'b'], ['aa', 'b']]; pal=[[True, True, False], [False, True, False], [False, False, True]]; path=['aa']; text='aab'; end=1

L16 visit: path.pop()
start=0; n=3; output=[['a', 'a', 'b'], ['aa', 'b']]; pal=[[True, True, False], [False, True, False], [False, False, True]]; path=[]; text='aab'; end=1

L12 visit: for end in range(start, n):
start=0; n=3; output=[['a', 'a', 'b'], ['aa', 'b']]; pal=[[True, True, False], [False, True, False], [False, False, True]]; path=[]; text='aab'; end=2

L17 palindrome_partitions: visit(0)
text='aab'; n=3; pal=[[True, True, False], [False, True, False], [False, False, True]]; i=0; j=2; output=[['a', 'a', 'b'], ['aa', 'b']]; path=[]

Result: [['a', 'a', 'b'], ['aa', 'b']]. The first two letters may be separate or one palindrome.

palindrome_partitions("")

L2 palindrome_partitions: n = len(text)
text=''; n=0

L3 palindrome_partitions: pal = [[False] * n for _ in range(n)]
text=''; n=0; pal=[]

L7 palindrome_partitions: output, path = [], []
text=''; n=0; pal=[]; output=[]; path=[]

L9 visit: if start == n:
start=0; n=0; output=[]; pal=[]; path=[]; text=''

L10 visit: output.append(path.copy())
start=0; n=0; output=[[]]; pal=[]; path=[]; text=''

L17 palindrome_partitions: visit(0)
text=''; n=0; pal=[]; output=[[]]; path=[]

Result: [[]]. The empty prefix already covers the whole input.

Why the solution is correct

The interval recurrence is correct from the inside outward. The search appends only palindromes and never leaves gaps or overlaps. Every valid partition defines a unique increasing sequence of cuts, all of which are tried. start strictly increases until the entire text is covered.

Time and space

O(n^2 + n*2^n) worst-case time and output storage; O(n^2) palindrome table plus O(n) recursive/path content auxiliary space. Substring copies are included in the bound.

Common mistakes

Treating the empty suffix as failure loses completed partitions. Mixing inclusive table ends with exclusive slices drops the final character.

Reasoning card

State: pal[i][j] describes inclusive substring text[i:j+1]. path partitions text[:start] completely into palindromes.

Invariant: Path partitions exactly the processed prefix.

Decision to rehearse: Choose the next palindromic prefix and recurse on the suffix.

Finish: Append its substring, recurse after its end, then undo

Transfer exercise

Find the minimum number of cuts using the same palindrome table but a dynamic program over prefixes.