BacktrackingStringDynamic Programming
Split a string into pieces so that every piece is a palindrome. Print every possible way to do it. Each line is one partition with its pieces separated by spaces, and the lines are in lexicographic order (comparing pieces from left to right, shorter piece first when one is a prefix of the other).
Input
A single string of lowercase letters.
Output
One partition per line.
Constraints
1 <= length <= 12
Example 1
Input
aab
Output
a a b aa b
a a b and aa b are the two ways.