Problem Statement

Palindrome Partitioning

You are given a string s. A palindrome is a word that reads the same forwards and backwards, like "aba" or "aa". Your job is to cut the string into pieces so that every single piece is a palindrome, and to find every possible way to do that. The tool we reach for here is backtracking. Backtracking means: try a choice, go deeper to see where it leads, and if it does not work out, undo the choice and try the next one. Picture exploring a maze where you mark your path with chalk, and when you hit a dead end you walk back, erase the last mark, and try a different turn. At each spot in the string we try every possible piece that can start there. If that piece is a palindrome, we keep it and solve the rest of the string the same way. When we have used up the whole string, we have one complete answer and we save it.

mediumStringBacktrackingBacktrackingTime: O(n * 2^n) · Space: O(n)

Signals to notice

partition string into palindromesenumerate all valid partitionsbacktracking with palindrome check

Brute force first

Without precomputation, each palindrome check is O(n) — total O(n × 2^n).

The key insight

Precompute isPalin[i][j]. Backtracking: at each position, try all cuts where the prefix is a palindrome. Recurse on the rest. O(n × 2^n) but with O(1) palindrome checks.

Trace it on `s = "aab"`

backtrack(0,[]): end=0 -> "a" palindrome, push -> path=["a"], recurse backtrack(1)
backtrack(1,["a"]): end=1 -> "a" palindrome, push -> path=["a","a"], recurse backtrack(2)
backtrack(2,["a","a"]): end=2 -> "b" palindrome, push -> path=["a","a","b"], recurse backtrack(3)
backtrack(3): start==len(s) -> record ["a","a","b"]; unwind/pop back to backtrack(1)
backtrack(1) end=2 -> "ab" not palindrome, skip; pop -> back to backtrack(0)
backtrack(0): end=1 -> "aa" palindrome, push -> path=["aa"], recurse backtrack(2)
backtrack(2,["aa"]): end=2 -> "b" palindrome -> path=["aa","b"], backtrack(3) records ["aa","b"]
backtrack(0): end=2 -> "aab" not palindrome, skip; return result=[["a","a","b"],["aa","b"]]

What must stay true

At each position, only palindromic prefixes are valid cuts. The precomputed table makes each check O(1), keeping the backtracking efficient.

Shape of the loop

function backtrack(start, path):
  if start == len(s): record copy of path; return
  for end in start..len(s)-1:
    if isPalindrome(start, end):
      path.push(s[start..end]); backtrack(end+1, path); path.pop()

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not precomputing palindromes — inline checking adds O(n) per check and slows the solution significantly.

Backtracking Pattern