Palindrome Partitioning
mediumTime: 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.
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.
Easy way to go wrong
Not precomputing palindromes — inline checking adds O(n) per check and slows the solution significantly.