Palindrome Partitioning

Backtracking with DP precomputation: isPalin[i][j] = (s[i]==s[j]) && isPalin[i+1][j-1] fills in O(n²). Then backtracking uses O(1) palindrome checks instead of O(n) per cut. Without precomputation it's O(n × 2^n); with it, the backtracking part is O(2^n × n) but palindrome checks are free.