Pattern visualizer

Palindrome Partitioning

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. Animated on: s = "aab". Return every way to cut s into palindromic pieces. Answer: ["a", "a", "b"] and ["aa", "b"]..

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

time O(n * 2^n)space O(n) recursion depth beyond the outputstep 1 / 11

[0]

[1]

[2]

line 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

Where to practice Backtracking

Practice Backtracking problems All Backtracking problems Back to roadmap