Palindrome Partitioning
mediumTime: O(n * 2^n)Space: O(n)
Recognize the pattern
partition string into palindromesenumerate all valid partitionsbacktracking with palindrome check
Brute force idea
Without precomputation, each palindrome check is O(n) — total O(n × 2^n).
Better approach
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.
Key invariant
At each position, only palindromic prefixes are valid cuts. The precomputed table makes each check O(1), keeping the backtracking efficient.
Watch out for
Not precomputing palindromes — inline checking adds O(n) per check and slows the solution significantly.