Approach Summary
Backtracking: try every prefix from the current position. If it's a palindrome, recurse on the remainder. Collect complete partitions.
How to Recognize This Pattern
- "All ways to partition string into palindromes"
- Backtracking + palindrome check precomputed with DP
Complexity Analysis
Time Complexity
O(n × 2ⁿ)
Space Complexity
O(n)
Tags
String Dynamic Programming Backtracking