Backtracking · LC #131

Palindrome Partitioning

Backtrack over all ways to cut a string; only extend the current partition when the next substring is a palindrome. Record the partition when the entire string is consumed.

mediumLC #131AMZ★★GOO★META★MSFT★
Mark as done
Confidence
Ask GPTPractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

Given string `s`, partition it so that every substring is a palindrome. Return all possible partitions.

Sample I/O

Input:  s = "aab"
Output: [["a","a","b"],["aa","b"]]

Input:  s = "a"
Output: [["a"]]

Intuition

How to Think About It

Intuition

Think of placing cut-points in the string. At each position, try all possible next cuts. Only recurse when the new segment is a palindrome - this is the pruning condition. When we reach the end of the string, the current list of palindromic segments is a valid partition.

Core Concept

bt(start, curr): if start==s.length, record curr. For end from start+1 to s.length: if s[start..end] is palindrome, push it, recurse bt(end, curr), pop. Palindrome check O(L). Precompute dp[i][j] to make checks O(1).

When to use

Partition a string into valid segments; any cut-based backtracking where each segment must satisfy a constraint.

When NOT to use

When you only need minimum cuts (Palindrome Partitioning II - LC 132 uses DP in O(n²)); when n > ~20 (output size explodes).

Key Insights

What to Know Cold

  • Palindrome check for each substring can be precomputed in O(n²) using 2D DP.
  • Only recurse when current segment IS a palindrome - this prunes non-viable branches early.
  • Record at start==s.length (leaf), not at every node like Subsets.
  • The end index goes to s.length (inclusive) - single characters are always palindromes.
  • DP precompute: dp[i][j] = true if s[i..j] is palindrome; saves repeated O(L) checks.

1 example

Worked Examples

All palindrome partitions of "aab"

Find all ways to cut "aab" so every part is a palindrome.

Backtracking with inline palindrome check; precompute DP for O(1) checks.

Output: [["a","a","b"],["aa","b"]]

Combines backtracking with a string property check; follow-up to DP minimum-cuts problem (LC 132).