Palindrome Partitioning

Cut only where the prefix is a palindrome, backtrack past the rest

time O(n * 2^n)space O(n) recursion depth beyond the output

A partition of s is just a choice of where to cut. At the current start index, try every possible next cut j and check whether s[start..j] is a palindrome with a two-pointer scan. A failing check is pruned immediately — there is no point extending a bad prefix further, since making it longer cannot make it a palindrome retroactively. A passing check commits the piece to path and recurses from j + 1; when start reaches the end of s, path itself is one full answer. Popping path after each recursive call is what lets the same start index try its next j once the deeper search is exhausted. The cells row is s's characters: a green cell is part of a committed piece (either already fixed earlier, or the one just accepted), a red cell is the trial range that just failed.

Details

Animated on: s = "aab". Return every way to cut s into palindromic pieces. Answer: ["a", "a", "b"] and ["aa", "b"].

Problem:Palindrome PartitioningMedium

Pattern:Backtracking with Constraints

Cut only where the prefix is a palindrome, backtrack past the rest

step 1 / 11

[0]

[1]

[2]

s <- "aab". Cut it into contiguous pieces where every piece is a palindrome — try each possible next cut from the current start, keep it only if it passes, and backtrack past the ones that fail.

Pseudocode

1FUNCTION partition(s)
2  n <- LENGTH(s), path <- EMPTY LIST, out <- EMPTY LIST
3  FUNCTION backtrack(start)
4    IF start = n
5      APPEND COPY(path) TO out
6      RETURN
7    FOR j <- start TO n - 1
8      sub <- s[start..j]
9      IF IS_PALINDROME(sub)
10        APPEND sub TO path
11        backtrack(j + 1)
12        REMOVE LAST FROM path
13  backtrack(0)
14  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 11 steps

s <- "aab". Cut it into contiguous pieces where every piece is a palindrome — try each possible next cut from the current start, keep it only if it passes, and backtrack past the ones that fail.
s[0..0] = "a" reads the same forwards and backwards, so it is a valid piece. Commit it to path and recurse from start=1.
s[1..1] = "a" reads the same forwards and backwards, so it is a valid piece. Commit it to path and recurse from start=2.
s[2..2] = "b" reads the same forwards and backwards, so it is a valid piece. Commit it to path and recurse from start=3.
start=3 reached the end of s, so path=["a", "a", "b"] is a complete partition — every piece already passed the palindrome check on the way here. Record it: 1 partition found so far.
s[1..2] = "ab" is not a palindrome — its outer characters differ. Extending the cut to j=2 is dead on arrival, so nothing is committed; try the next j.
s[0..1] = "aa" reads the same forwards and backwards, so it is a valid piece. Commit it to path and recurse from start=2.
s[2..2] = "b" reads the same forwards and backwards, so it is a valid piece. Commit it to path and recurse from start=3.
start=3 reached the end of s, so path=["aa", "b"] is a complete partition — every piece already passed the palindrome check on the way here. Record it: 2 partitions found so far.
s[0..2] = "aab" is not a palindrome — its outer characters differ. Extending the cut to j=2 is dead on arrival, so nothing is committed; try the next j.
Every cut from start=0 has been tried. 2 palindrome partitions of "aab": ["a", "a", "b"] and ["aa", "b"].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Palindrome Partitioning in the editor All Backtracking problems Back to roadmap